1 /* Nested function decomposition for trees.
2 Copyright (C) 2004 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
23 #include "coretypes.h"
29 #include "tree-dump.h"
30 #include "tree-inline.h"
31 #include "tree-gimple.h"
32 #include "tree-iterator.h"
33 #include "tree-flow.h"
36 #include "langhooks.h"
40 /* The object of this pass is to lower the representation of a set of nested
41 functions in order to expose all of the gory details of the various
42 nonlocal references. We want to do this sooner rather than later, in
43 order to give us more freedom in emitting all of the functions in question.
45 Back in olden times, when gcc was young, we developed an insanely
46 complicated scheme whereby variables which were referenced nonlocally
47 were forced to live in the stack of the declaring function, and then
48 the nested functions magically discovered where these variables were
49 placed. In order for this scheme to function properly, it required
50 that the outer function be partially expanded, then we switch to
51 compiling the inner function, and once done with those we switch back
52 to compiling the outer function. Such delicate ordering requirements
53 makes it difficult to do whole translation unit optimizations
54 involving such functions.
56 The implementation here is much more direct. Everything that can be
57 referenced by an inner function is a member of an explicitly created
58 structure herein called the "nonlocal frame struct". The incoming
59 static chain for a nested function is a pointer to this struct in
60 the parent. In this way, we settle on known offsets from a known
61 base, and so are decoupled from the logic that places objects in the
62 function's stack frame. More importantly, we don't have to wait for
63 that to happen -- since the compilation of the inner function is no
64 longer tied to a real stack frame, the nonlocal frame struct can be
65 allocated anywhere. Which means that the outer function is now
68 Theory of operation here is very simple. Iterate over all the
69 statements in all the functions (depth first) several times,
70 allocating structures and fields on demand. In general we want to
71 examine inner functions first, so that we can avoid making changes
72 to outer functions which are unnecessary.
74 The order of the passes matters a bit, in that later passes will be
75 skipped if it is discovered that the functions don't actually interact
76 at all. That is, they're nested in the lexical sense but could have
77 been written as independent functions without change. */
88 struct nesting_info *outer;
89 struct nesting_info *inner;
90 struct nesting_info *next;
94 tree new_local_var_chain;
101 bool any_parm_remapped;
102 bool any_tramp_created;
106 /* Hashing and equality functions for nesting_info->var_map. */
109 var_map_hash (const void *x)
111 const struct var_map_elt *a = x;
112 return htab_hash_pointer (a->old);
116 var_map_eq (const void *x, const void *y)
118 const struct var_map_elt *a = x;
119 const struct var_map_elt *b = y;
120 return a->old == b->old;
123 /* We're working in so many different function contexts simultaneously,
124 that create_tmp_var is dangerous. Prevent mishap. */
125 #define create_tmp_var cant_use_create_tmp_var_here_dummy
127 /* Like create_tmp_var, except record the variable for registration at
128 the given nesting level. */
131 create_tmp_var_for (struct nesting_info *info, tree type, const char *prefix)
135 /* If the type is of variable size or a type which must be created by the
136 frontend, something is wrong. Note that we explicitly allow
137 incomplete types here, since we create them ourselves here. */
138 gcc_assert (!TREE_ADDRESSABLE (type));
139 gcc_assert (!TYPE_SIZE_UNIT (type)
140 || TREE_CODE (TYPE_SIZE_UNIT (type)) == INTEGER_CST);
142 tmp_var = create_tmp_var_raw (type, prefix);
143 DECL_CONTEXT (tmp_var) = info->context;
144 TREE_CHAIN (tmp_var) = info->new_local_var_chain;
145 DECL_SEEN_IN_BIND_EXPR_P (tmp_var) = 1;
146 info->new_local_var_chain = tmp_var;
151 /* Take the address of EXP. Mark it for addressability as necessary. */
154 build_addr (tree exp)
158 while (TREE_CODE (base) == REALPART_EXPR || TREE_CODE (base) == IMAGPART_EXPR
159 || handled_component_p (base))
160 base = TREE_OPERAND (base, 0);
163 TREE_ADDRESSABLE (base) = 1;
165 return build1 (ADDR_EXPR, build_pointer_type (TREE_TYPE (exp)), exp);
168 /* Insert FIELD into TYPE, sorted by alignment requirements. */
171 insert_field_into_struct (tree type, tree field)
175 DECL_CONTEXT (field) = type;
177 for (p = &TYPE_FIELDS (type); *p ; p = &TREE_CHAIN (*p))
178 if (DECL_ALIGN (field) >= DECL_ALIGN (*p))
181 TREE_CHAIN (field) = *p;
185 /* Build or return the RECORD_TYPE that describes the frame state that is
186 shared between INFO->CONTEXT and its nested functions. This record will
187 not be complete until finalize_nesting_tree; up until that point we'll
188 be adding fields as necessary.
190 We also build the DECL that represents this frame in the function. */
193 get_frame_type (struct nesting_info *info)
195 tree type = info->frame_type;
200 type = make_node (RECORD_TYPE);
202 name = concat ("FRAME.",
203 IDENTIFIER_POINTER (DECL_NAME (info->context)),
205 TYPE_NAME (type) = get_identifier (name);
208 info->frame_type = type;
209 info->frame_decl = create_tmp_var_for (info, type, "FRAME");
214 /* Return true if DECL should be referenced by pointer in the non-local
218 use_pointer_in_frame (tree decl)
220 if (TREE_CODE (decl) == PARM_DECL)
222 /* It's illegal to copy TREE_ADDRESSABLE, impossible to copy variable
223 sized decls, and inefficient to copy large aggregates. Don't bother
224 moving anything but scalar variables. */
225 return AGGREGATE_TYPE_P (TREE_TYPE (decl));
229 /* Variable sized types make things "interesting" in the frame. */
230 return DECL_SIZE (decl) == NULL || !TREE_CONSTANT (DECL_SIZE (decl));
234 /* Given DECL, a non-locally accessed variable, find or create a field
235 in the non-local frame structure for the given nesting context. */
238 lookup_field_for_decl (struct nesting_info *info, tree decl,
239 enum insert_option insert)
241 struct var_map_elt *elt, dummy;
246 slot = htab_find_slot (info->var_map, &dummy, insert);
249 gcc_assert (insert != INSERT);
254 if (!elt && insert == INSERT)
256 field = make_node (FIELD_DECL);
257 DECL_NAME (field) = DECL_NAME (decl);
259 if (use_pointer_in_frame (decl))
261 TREE_TYPE (field) = build_pointer_type (TREE_TYPE (decl));
262 DECL_ALIGN (field) = TYPE_ALIGN (TREE_TYPE (field));
263 DECL_NONADDRESSABLE_P (field) = 1;
267 TREE_TYPE (field) = TREE_TYPE (decl);
268 DECL_SOURCE_LOCATION (field) = DECL_SOURCE_LOCATION (decl);
269 DECL_ALIGN (field) = DECL_ALIGN (decl);
270 DECL_USER_ALIGN (field) = DECL_USER_ALIGN (decl);
271 TREE_ADDRESSABLE (field) = TREE_ADDRESSABLE (decl);
272 DECL_NONADDRESSABLE_P (field) = !TREE_ADDRESSABLE (decl);
273 TREE_THIS_VOLATILE (field) = TREE_THIS_VOLATILE (decl);
276 insert_field_into_struct (get_frame_type (info), field);
278 elt = xmalloc (sizeof (*elt));
283 if (TREE_CODE (decl) == PARM_DECL)
284 info->any_parm_remapped = true;
287 field = elt ? elt->new : NULL;
292 /* Build or return the variable that holds the static chain within
293 INFO->CONTEXT. This variable may only be used within INFO->CONTEXT. */
296 get_chain_decl (struct nesting_info *info)
298 tree decl = info->chain_decl;
303 type = get_frame_type (info->outer);
304 type = build_pointer_type (type);
306 /* Note that this variable is *not* entered into any BIND_EXPR;
307 the construction of this variable is handled specially in
308 expand_function_start and initialize_inlined_parameters.
309 Note also that it's represented as a parameter. This is more
310 close to the truth, since the initial value does come from
312 decl = build_decl (PARM_DECL, create_tmp_var_name ("CHAIN"), type);
313 DECL_ARTIFICIAL (decl) = 1;
314 DECL_IGNORED_P (decl) = 1;
315 TREE_USED (decl) = 1;
316 DECL_CONTEXT (decl) = info->context;
317 DECL_ARG_TYPE (decl) = type;
319 /* Tell tree-inline.c that we never write to this variable, so
320 it can copy-prop the replacement value immediately. */
321 TREE_READONLY (decl) = 1;
323 info->chain_decl = decl;
328 /* Build or return the field within the non-local frame state that holds
329 the static chain for INFO->CONTEXT. This is the way to walk back up
330 multiple nesting levels. */
333 get_chain_field (struct nesting_info *info)
335 tree field = info->chain_field;
338 tree type = build_pointer_type (get_frame_type (info->outer));
340 field = make_node (FIELD_DECL);
341 DECL_NAME (field) = get_identifier ("__chain");
342 TREE_TYPE (field) = type;
343 DECL_ALIGN (field) = TYPE_ALIGN (type);
344 DECL_NONADDRESSABLE_P (field) = 1;
346 insert_field_into_struct (get_frame_type (info), field);
348 info->chain_field = field;
353 /* Copy EXP into a temporary. Allocate the temporary in the context of
354 INFO and insert the initialization statement before TSI. */
357 init_tmp_var (struct nesting_info *info, tree exp, tree_stmt_iterator *tsi)
361 t = create_tmp_var_for (info, TREE_TYPE (exp), NULL);
362 stmt = build (MODIFY_EXPR, TREE_TYPE (t), t, exp);
363 SET_EXPR_LOCUS (stmt, EXPR_LOCUS (tsi_stmt (*tsi)));
364 tsi_link_before (tsi, stmt, TSI_SAME_STMT);
369 /* Similarly, but only do so to force EXP to satisfy is_gimple_val. */
372 tsi_gimplify_val (struct nesting_info *info, tree exp, tree_stmt_iterator *tsi)
374 if (is_gimple_val (exp))
377 return init_tmp_var (info, exp, tsi);
380 /* Build or return the type used to represent a nested function trampoline. */
382 static GTY(()) tree trampoline_type;
385 get_trampoline_type (void)
388 unsigned align, size;
391 return trampoline_type;
393 align = TRAMPOLINE_ALIGNMENT;
394 size = TRAMPOLINE_SIZE;
396 /* If we won't be able to guarantee alignment simply via TYPE_ALIGN,
397 then allocate extra space so that we can do dynamic alignment. */
398 if (align > STACK_BOUNDARY)
400 size += ((align/BITS_PER_UNIT) - 1) & -(STACK_BOUNDARY/BITS_PER_UNIT);
401 align = STACK_BOUNDARY;
404 t = build_index_type (build_int_cst (NULL_TREE, size - 1));
405 t = build_array_type (char_type_node, t);
406 t = build_decl (FIELD_DECL, get_identifier ("__data"), t);
407 DECL_ALIGN (t) = align;
408 DECL_USER_ALIGN (t) = 1;
410 record = make_node (RECORD_TYPE);
411 TYPE_NAME (record) = get_identifier ("__builtin_trampoline");
412 TYPE_FIELDS (record) = t;
413 layout_type (record);
418 /* Given DECL, a nested function, find or create a field in the non-local
419 frame structure for a trampoline for this function. */
422 lookup_tramp_for_decl (struct nesting_info *info, tree decl,
423 enum insert_option insert)
425 struct var_map_elt *elt, dummy;
430 slot = htab_find_slot (info->var_map, &dummy, insert);
433 gcc_assert (insert != INSERT);
438 if (!elt && insert == INSERT)
440 field = make_node (FIELD_DECL);
441 DECL_NAME (field) = DECL_NAME (decl);
442 TREE_TYPE (field) = get_trampoline_type ();
443 TREE_ADDRESSABLE (field) = 1;
445 insert_field_into_struct (get_frame_type (info), field);
447 elt = xmalloc (sizeof (*elt));
452 info->any_tramp_created = true;
455 field = elt ? elt->new : NULL;
460 /* Build or return the field within the non-local frame state that holds
461 the non-local goto "jmp_buf". The buffer itself is maintained by the
462 rtl middle-end as dynamic stack space is allocated. */
465 get_nl_goto_field (struct nesting_info *info)
467 tree field = info->nl_goto_field;
473 /* For __builtin_nonlocal_goto, we need N words. The first is the
474 frame pointer, the rest is for the target's stack pointer save
475 area. The number of words is controlled by STACK_SAVEAREA_MODE;
476 not the best interface, but it'll do for now. */
477 if (Pmode == ptr_mode)
478 type = ptr_type_node;
480 type = lang_hooks.types.type_for_mode (Pmode, 1);
482 size = GET_MODE_SIZE (STACK_SAVEAREA_MODE (SAVE_NONLOCAL));
483 size = size / GET_MODE_SIZE (Pmode);
486 type = build_array_type
487 (type, build_index_type (build_int_cst (NULL_TREE, size)));
489 field = make_node (FIELD_DECL);
490 DECL_NAME (field) = get_identifier ("__nl_goto_buf");
491 TREE_TYPE (field) = type;
492 DECL_ALIGN (field) = TYPE_ALIGN (type);
493 TREE_ADDRESSABLE (field) = 1;
495 insert_field_into_struct (get_frame_type (info), field);
497 info->nl_goto_field = field;
503 /* Convenience routines to walk all statements of a gimple function.
505 For each statement, we invoke CALLBACK via walk_tree. The passed
506 data is a walk_stmt_info structure. Of note here is a TSI that
507 points to the current statement being walked. The VAL_ONLY flag
508 that indicates whether the *TP being examined may be replaced
509 with something that matches is_gimple_val (if true) or something
510 slightly more complicated (if false). "Something" technically
511 means the common subset of is_gimple_lvalue and is_gimple_rhs,
512 but we never try to form anything more complicated than that, so
513 we don't bother checking. */
515 struct walk_stmt_info
517 walk_tree_fn callback;
518 tree_stmt_iterator tsi;
519 struct nesting_info *info;
524 /* A subroutine of walk_function. Iterate over all sub-statements of *TP. */
527 walk_stmts (struct walk_stmt_info *wi, tree *tp)
533 switch (TREE_CODE (t))
537 tree_stmt_iterator i;
538 for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
541 walk_stmts (wi, tsi_stmt_ptr (i));
547 walk_tree (&COND_EXPR_COND (t), wi->callback, wi, NULL);
548 walk_stmts (wi, &COND_EXPR_THEN (t));
549 walk_stmts (wi, &COND_EXPR_ELSE (t));
552 walk_stmts (wi, &CATCH_BODY (t));
555 walk_stmts (wi, &EH_FILTER_FAILURE (t));
558 case TRY_FINALLY_EXPR:
559 walk_stmts (wi, &TREE_OPERAND (t, 0));
560 walk_stmts (wi, &TREE_OPERAND (t, 1));
563 walk_stmts (wi, &BIND_EXPR_BODY (t));
567 walk_stmts (wi, &TREE_OPERAND (t, 0));
571 /* The immediate arguments of a MODIFY_EXPR may use COMPONENT_REF. */
572 wi->val_only = false;
573 walk_tree (&TREE_OPERAND (t, 0), wi->callback, wi, NULL);
574 wi->val_only = false;
575 walk_tree (&TREE_OPERAND (t, 1), wi->callback, wi, NULL);
581 walk_tree (tp, wi->callback, wi, NULL);
586 /* Invoke CALLBACK on all statements of INFO->CONTEXT. */
589 walk_function (walk_tree_fn callback, struct nesting_info *info)
591 struct walk_stmt_info wi;
593 memset (&wi, 0, sizeof (wi));
594 wi.callback = callback;
598 walk_stmts (&wi, &DECL_SAVED_TREE (info->context));
601 /* Similarly for ROOT and all functions nested underneath, depth first. */
604 walk_all_functions (walk_tree_fn callback, struct nesting_info *root)
609 walk_all_functions (callback, root->inner);
610 walk_function (callback, root);
616 /* We have to check for a fairly pathalogical case. The operands of function
617 nested function are to be interpreted in the context of the enclosing
618 function. So if any are variably-sized, they will get remapped when the
619 enclosing function is inlined. But that remapping would also have to be
620 done in the types of the PARM_DECLs of the nested function, meaning the
621 argument types of that function will disagree with the arguments in the
622 calls to that function. So we'd either have to make a copy of the nested
623 function corresponding to each time the enclosing function was inlined or
624 add a VIEW_CONVERT_EXPR to each such operand for each call to the nested
625 function. The former is not practical. The latter would still require
626 detecting this case to know when to add the conversions. So, for now at
627 least, we don't inline such an enclosing function.
629 We have to do that check recursively, so here return indicating whether
630 FNDECL has such a nested function. ORIG_FN is the function we were
631 trying to inline to use for checking whether any argument is variably
632 modified by anything in it.
634 It would be better to do this in tree-inline.c so that we could give
635 the appropriate warning for why a function can't be inlined, but that's
636 too late since the nesting structure has already been flattened and
637 adding a flag just to record this fact seems a waste of a flag. */
640 check_for_nested_with_variably_modified (tree fndecl, tree orig_fndecl)
642 struct cgraph_node *cgn = cgraph_node (fndecl);
645 for (cgn = cgn->nested; cgn ; cgn = cgn->next_nested)
647 for (arg = DECL_ARGUMENTS (cgn->decl); arg; arg = TREE_CHAIN (arg))
648 if (variably_modified_type_p (TREE_TYPE (arg), 0), orig_fndecl)
651 if (check_for_nested_with_variably_modified (cgn->decl, orig_fndecl))
658 /* Construct our local datastructure describing the function nesting
659 tree rooted by CGN. */
661 static struct nesting_info *
662 create_nesting_tree (struct cgraph_node *cgn)
664 struct nesting_info *info = xcalloc (1, sizeof (*info));
665 info->var_map = htab_create (7, var_map_hash, var_map_eq, free);
666 info->context = cgn->decl;
668 for (cgn = cgn->nested; cgn ; cgn = cgn->next_nested)
670 struct nesting_info *sub = create_nesting_tree (cgn);
672 sub->next = info->inner;
676 /* See discussion at check_for_nested_with_variably_modified for a
677 discussion of why this has to be here. */
678 if (check_for_nested_with_variably_modified (info->context, info->context))
679 DECL_UNINLINABLE (info->context) = true;
684 /* Return an expression computing the static chain for TARGET_CONTEXT
685 from INFO->CONTEXT. Insert any necessary computations before TSI. */
688 get_static_chain (struct nesting_info *info, tree target_context,
689 tree_stmt_iterator *tsi)
691 struct nesting_info *i;
694 if (info->context == target_context)
696 x = build_addr (info->frame_decl);
700 x = get_chain_decl (info);
702 for (i = info->outer; i->context != target_context; i = i->outer)
704 tree field = get_chain_field (i);
706 x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
707 x = build (COMPONENT_REF, TREE_TYPE (field), x, field, NULL_TREE);
708 x = init_tmp_var (info, x, tsi);
715 /* Return an expression referencing FIELD from TARGET_CONTEXT's non-local
716 frame as seen from INFO->CONTEXT. Insert any necessary computations
720 get_frame_field (struct nesting_info *info, tree target_context,
721 tree field, tree_stmt_iterator *tsi)
723 struct nesting_info *i;
726 if (info->context == target_context)
728 /* Make sure frame_decl gets created. */
729 (void) get_frame_type (info);
730 x = info->frame_decl;
734 x = get_chain_decl (info);
736 for (i = info->outer; i->context != target_context; i = i->outer)
738 tree field = get_chain_field (i);
740 x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
741 x = build (COMPONENT_REF, TREE_TYPE (field), x, field, NULL_TREE);
742 x = init_tmp_var (info, x, tsi);
745 x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
748 x = build (COMPONENT_REF, TREE_TYPE (field), x, field, NULL_TREE);
752 /* Called via walk_function+walk_tree, rewrite all references to VAR
753 and PARM_DECLs that belong to outer functions.
755 The rewrite will involve some number of structure accesses back up
756 the static chain. E.g. for a variable FOO up one nesting level it'll
757 be CHAIN->FOO. For two levels it'll be CHAIN->__chain->FOO. Further
758 indirections apply to decls for which use_pointer_in_frame is true. */
761 convert_nonlocal_reference (tree *tp, int *walk_subtrees, void *data)
763 struct walk_stmt_info *wi = data;
764 struct nesting_info *info = wi->info;
768 switch (TREE_CODE (t))
771 /* Non-automatic variables are never processed. */
772 if (TREE_STATIC (t) || DECL_EXTERNAL (t))
777 if (decl_function_context (t) != info->context)
779 tree target_context = decl_function_context (t);
780 struct nesting_info *i;
784 for (i = info->outer; i->context != target_context; i = i->outer)
786 x = lookup_field_for_decl (i, t, INSERT);
787 x = get_frame_field (info, target_context, x, &wi->tsi);
788 if (use_pointer_in_frame (t))
790 x = init_tmp_var (info, x, &wi->tsi);
791 x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
794 x = init_tmp_var (info, x, &wi->tsi);
801 /* Don't walk non-local gotos for now. */
802 if (TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL)
810 /* We're taking the address of a label from a parent function, but
811 this is not itself a non-local goto. Mark the label such that it
812 will not be deleted, much as we would with a label address in
814 if (decl_function_context (t) != info->context)
815 FORCED_LABEL (t) = 1;
820 bool save_val_only = wi->val_only;
823 wi->val_only = false;
824 walk_tree (&TREE_OPERAND (t, 0), convert_nonlocal_reference, wi, NULL);
829 /* If we changed anything, then TREE_INVARIANT is be wrong,
830 since we're no longer directly referencing a decl. */
831 recompute_tree_invarant_for_addr_expr (t);
833 /* If the callback converted the address argument in a context
834 where we only accept variables (and min_invariant, presumably),
835 then compute the address into a temporary. */
837 *tp = tsi_gimplify_val (wi->info, t, &wi->tsi);
846 case ARRAY_RANGE_REF:
848 /* Go down this entire nest and just look at the final prefix and
849 anything that describes the references. Otherwise, we lose track
850 of whether a NOP_EXPR or VIEW_CONVERT_EXPR needs a simple value. */
852 for (; handled_component_p (t)
853 || TREE_CODE (t) == REALPART_EXPR || TREE_CODE (t) == IMAGPART_EXPR;
854 tp = &TREE_OPERAND (t, 0), t = *tp)
856 if (TREE_CODE (t) == COMPONENT_REF)
857 walk_tree (&TREE_OPERAND (t, 2), convert_nonlocal_reference, wi,
859 else if (TREE_CODE (t) == ARRAY_REF
860 || TREE_CODE (t) == ARRAY_RANGE_REF)
862 walk_tree (&TREE_OPERAND (t, 1), convert_nonlocal_reference, wi,
864 walk_tree (&TREE_OPERAND (t, 2), convert_nonlocal_reference, wi,
866 walk_tree (&TREE_OPERAND (t, 3), convert_nonlocal_reference, wi,
869 else if (TREE_CODE (t) == BIT_FIELD_REF)
871 walk_tree (&TREE_OPERAND (t, 1), convert_nonlocal_reference, wi,
873 walk_tree (&TREE_OPERAND (t, 2), convert_nonlocal_reference, wi,
877 wi->val_only = false;
878 walk_tree (tp, convert_nonlocal_reference, wi, NULL);
882 if (!IS_TYPE_OR_DECL_P (t))
893 /* Called via walk_function+walk_tree, rewrite all references to VAR
894 and PARM_DECLs that were referenced by inner nested functions.
895 The rewrite will be a structure reference to the local frame variable. */
898 convert_local_reference (tree *tp, int *walk_subtrees, void *data)
900 struct walk_stmt_info *wi = data;
901 struct nesting_info *info = wi->info;
902 tree t = *tp, field, x;
904 switch (TREE_CODE (t))
907 /* Non-automatic variables are never processed. */
908 if (TREE_STATIC (t) || DECL_EXTERNAL (t))
913 if (decl_function_context (t) == info->context)
915 /* If we copied a pointer to the frame, then the original decl
916 is used unchanged in the parent function. */
917 if (use_pointer_in_frame (t))
920 /* No need to transform anything if no child references the
922 field = lookup_field_for_decl (info, t, NO_INSERT);
927 x = get_frame_field (info, info->context, field, &wi->tsi);
929 x = init_tmp_var (info, x, &wi->tsi);
936 bool save_val_only = wi->val_only;
939 wi->val_only = false;
940 walk_tree (&TREE_OPERAND (t, 0), convert_local_reference, wi, NULL);
941 wi->val_only = save_val_only;
943 /* If we converted anything ... */
946 /* Then the frame decl is now addressable. */
947 TREE_ADDRESSABLE (info->frame_decl) = 1;
949 recompute_tree_invarant_for_addr_expr (t);
951 /* If we are in a context where we only accept values, then
952 compute the address into a temporary. */
954 *tp = tsi_gimplify_val (wi->info, t, &wi->tsi);
963 case ARRAY_RANGE_REF:
965 /* Go down this entire nest and just look at the final prefix and
966 anything that describes the references. Otherwise, we lose track
967 of whether a NOP_EXPR or VIEW_CONVERT_EXPR needs a simple value. */
969 for (; handled_component_p (t)
970 || TREE_CODE (t) == REALPART_EXPR || TREE_CODE (t) == IMAGPART_EXPR;
971 tp = &TREE_OPERAND (t, 0), t = *tp)
973 if (TREE_CODE (t) == COMPONENT_REF)
974 walk_tree (&TREE_OPERAND (t, 2), convert_local_reference, wi,
976 else if (TREE_CODE (t) == ARRAY_REF
977 || TREE_CODE (t) == ARRAY_RANGE_REF)
979 walk_tree (&TREE_OPERAND (t, 1), convert_local_reference, wi,
981 walk_tree (&TREE_OPERAND (t, 2), convert_local_reference, wi,
983 walk_tree (&TREE_OPERAND (t, 3), convert_local_reference, wi,
986 else if (TREE_CODE (t) == BIT_FIELD_REF)
988 walk_tree (&TREE_OPERAND (t, 1), convert_local_reference, wi,
990 walk_tree (&TREE_OPERAND (t, 2), convert_local_reference, wi,
994 wi->val_only = false;
995 walk_tree (tp, convert_local_reference, wi, NULL);
999 if (!IS_TYPE_OR_DECL_P (t))
1002 wi->val_only = true;
1010 /* Called via walk_function+walk_tree, rewrite all GOTO_EXPRs that
1011 reference labels from outer functions. The rewrite will be a
1012 call to __builtin_nonlocal_goto. */
1015 convert_nl_goto_reference (tree *tp, int *walk_subtrees, void *data)
1017 struct walk_stmt_info *wi = data;
1018 struct nesting_info *info = wi->info, *i;
1019 tree t = *tp, label, new_label, target_context, x, arg, field;
1020 struct var_map_elt *elt;
1024 if (TREE_CODE (t) != GOTO_EXPR)
1026 label = GOTO_DESTINATION (t);
1027 if (TREE_CODE (label) != LABEL_DECL)
1029 target_context = decl_function_context (label);
1030 if (target_context == info->context)
1033 for (i = info->outer; target_context != i->context; i = i->outer)
1036 /* The original user label may also be use for a normal goto, therefore
1037 we must create a new label that will actually receive the abnormal
1038 control transfer. This new label will be marked LABEL_NONLOCAL; this
1039 mark will trigger proper behavior in the cfg, as well as cause the
1040 (hairy target-specific) non-local goto receiver code to be generated
1041 when we expand rtl. */
1042 new_label = create_artificial_label ();
1043 DECL_NONLOCAL (new_label) = 1;
1045 /* Enter this association into var_map so that we can insert the new
1046 label into the IL during a second pass. */
1047 elt = xmalloc (sizeof (*elt));
1049 elt->new = new_label;
1050 slot = htab_find_slot (i->var_map, elt, INSERT);
1053 /* Build: __builtin_nl_goto(new_label, &chain->nl_goto_field). */
1054 field = get_nl_goto_field (i);
1055 x = get_frame_field (info, target_context, field, &wi->tsi);
1057 x = tsi_gimplify_val (info, x, &wi->tsi);
1058 arg = tree_cons (NULL, x, NULL);
1059 x = build_addr (new_label);
1060 arg = tree_cons (NULL, x, arg);
1061 x = implicit_built_in_decls[BUILT_IN_NONLOCAL_GOTO];
1062 x = build_function_call_expr (x, arg);
1064 SET_EXPR_LOCUS (x, EXPR_LOCUS (tsi_stmt (wi->tsi)));
1065 *tsi_stmt_ptr (wi->tsi) = x;
1070 /* Called via walk_function+walk_tree, rewrite all LABEL_EXPRs that
1071 are referenced via nonlocal goto from a nested function. The rewrite
1072 will involve installing a newly generated DECL_NONLOCAL label, and
1073 (potentially) a branch around the rtl gunk that is assumed to be
1074 attached to such a label. */
1077 convert_nl_goto_receiver (tree *tp, int *walk_subtrees, void *data)
1079 struct walk_stmt_info *wi = data;
1080 struct nesting_info *info = wi->info;
1081 tree t = *tp, label, new_label, x;
1082 struct var_map_elt *elt, dummy;
1083 tree_stmt_iterator tmp_tsi;
1086 if (TREE_CODE (t) != LABEL_EXPR)
1088 label = LABEL_EXPR_LABEL (t);
1091 elt = htab_find (info->var_map, &dummy);
1094 new_label = elt->new;
1096 /* If there's any possibility that the previous statement falls through,
1097 then we must branch around the new non-local label. */
1099 tsi_prev (&tmp_tsi);
1100 if (tsi_end_p (tmp_tsi) || block_may_fallthru (tsi_stmt (tmp_tsi)))
1102 x = build1 (GOTO_EXPR, void_type_node, label);
1103 tsi_link_before (&wi->tsi, x, TSI_SAME_STMT);
1105 x = build1 (LABEL_EXPR, void_type_node, new_label);
1106 tsi_link_before (&wi->tsi, x, TSI_SAME_STMT);
1111 /* Called via walk_function+walk_tree, rewrite all references to addresses
1112 of nested functions that require the use of trampolines. The rewrite
1113 will involve a reference a trampoline generated for the occasion. */
1116 convert_tramp_reference (tree *tp, int *walk_subtrees, void *data)
1118 struct walk_stmt_info *wi = data;
1119 struct nesting_info *info = wi->info, *i;
1120 tree t = *tp, decl, target_context, x, arg;
1123 switch (TREE_CODE (t))
1127 T.1 = &CHAIN->tramp;
1128 T.2 = __builtin_adjust_trampoline (T.1);
1129 T.3 = (func_type)T.2;
1132 decl = TREE_OPERAND (t, 0);
1133 if (TREE_CODE (decl) != FUNCTION_DECL)
1136 /* Only need to process nested functions. */
1137 target_context = decl_function_context (decl);
1138 if (!target_context)
1141 /* If the nested function doesn't use a static chain, then
1142 it doesn't need a trampoline. */
1143 if (DECL_NO_STATIC_CHAIN (decl))
1146 /* Lookup the immediate parent of the callee, as that's where
1147 we need to insert the trampoline. */
1148 for (i = info; i->context != target_context; i = i->outer)
1150 x = lookup_tramp_for_decl (i, decl, INSERT);
1152 /* Compute the address of the field holding the trampoline. */
1153 x = get_frame_field (info, target_context, x, &wi->tsi);
1155 x = tsi_gimplify_val (info, x, &wi->tsi);
1156 arg = tree_cons (NULL, x, NULL);
1158 /* Do machine-specific ugliness. Normally this will involve
1159 computing extra alignment, but it can really be anything. */
1160 x = implicit_built_in_decls[BUILT_IN_ADJUST_TRAMPOLINE];
1161 x = build_function_call_expr (x, arg);
1162 x = init_tmp_var (info, x, &wi->tsi);
1164 /* Cast back to the proper function type. */
1165 x = build1 (NOP_EXPR, TREE_TYPE (t), x);
1166 x = init_tmp_var (info, x, &wi->tsi);
1172 /* Only walk call arguments, lest we generate trampolines for
1174 walk_tree (&TREE_OPERAND (t, 1), convert_tramp_reference, wi, NULL);
1178 if (!IS_TYPE_OR_DECL_P (t))
1186 /* Called via walk_function+walk_tree, rewrite all CALL_EXPRs that
1187 reference nested functions to make sure that the static chain is
1188 set up properly for the call. */
1191 convert_call_expr (tree *tp, int *walk_subtrees, void *data)
1193 struct walk_stmt_info *wi = data;
1194 struct nesting_info *info = wi->info;
1195 tree t = *tp, decl, target_context;
1198 switch (TREE_CODE (t))
1201 decl = get_callee_fndecl (t);
1204 target_context = decl_function_context (decl);
1205 if (target_context && !DECL_NO_STATIC_CHAIN (decl))
1207 = get_static_chain (info, target_context, &wi->tsi);
1212 case WITH_SIZE_EXPR:
1213 /* Only return modify and with_size_expr may contain calls. */
1224 /* Walk the nesting tree starting with ROOT, depth first. Convert all
1225 trampolines and call expressions. On the way back up, determine if
1226 a nested function actually uses its static chain; if not, remember that. */
1229 convert_all_function_calls (struct nesting_info *root)
1234 convert_all_function_calls (root->inner);
1236 walk_function (convert_tramp_reference, root);
1237 walk_function (convert_call_expr, root);
1239 /* If the function does not use a static chain, then remember that. */
1240 if (root->outer && !root->chain_decl && !root->chain_field)
1241 DECL_NO_STATIC_CHAIN (root->context) = 1;
1243 gcc_assert (!DECL_NO_STATIC_CHAIN (root->context));
1250 /* Do "everything else" to clean up or complete state collected by the
1251 various walking passes -- lay out the types and decls, generate code
1252 to initialize the frame decl, store critical expressions in the
1253 struct function for rtl to find. */
1256 finalize_nesting_tree_1 (struct nesting_info *root)
1258 tree stmt_list = NULL;
1259 tree context = root->context;
1260 struct function *sf;
1261 struct cgraph_node *node;
1263 /* If we created a non-local frame type or decl, we need to lay them
1264 out at this time. */
1265 if (root->frame_type)
1267 layout_type (root->frame_type);
1268 layout_decl (root->frame_decl, 0);
1271 /* If any parameters were referenced non-locally, then we need to
1272 insert a copy. Likewise, if any variables were referenced by
1273 pointer, we need to initialize the address. */
1274 if (root->any_parm_remapped)
1277 for (p = DECL_ARGUMENTS (context); p ; p = TREE_CHAIN (p))
1281 field = lookup_field_for_decl (root, p, NO_INSERT);
1285 if (use_pointer_in_frame (p))
1290 y = build (COMPONENT_REF, TREE_TYPE (field),
1291 root->frame_decl, field, NULL_TREE);
1292 x = build (MODIFY_EXPR, TREE_TYPE (field), y, x);
1293 append_to_statement_list (x, &stmt_list);
1297 /* If a chain_field was created, then it needs to be initialized
1299 if (root->chain_field)
1301 tree x = build (COMPONENT_REF, TREE_TYPE (root->chain_field),
1302 root->frame_decl, root->chain_field, NULL_TREE);
1303 x = build (MODIFY_EXPR, TREE_TYPE (x), x, get_chain_decl (root));
1304 append_to_statement_list (x, &stmt_list);
1307 /* If trampolines were created, then we need to initialize them. */
1308 if (root->any_tramp_created)
1310 struct nesting_info *i;
1311 for (i = root->inner; i ; i = i->next)
1315 field = lookup_tramp_for_decl (root, i->context, NO_INSERT);
1319 if (DECL_NO_STATIC_CHAIN (i->context))
1320 x = null_pointer_node;
1322 x = build_addr (root->frame_decl);
1323 arg = tree_cons (NULL, x, NULL);
1325 x = build_addr (i->context);
1326 arg = tree_cons (NULL, x, arg);
1328 x = build (COMPONENT_REF, TREE_TYPE (field),
1329 root->frame_decl, field, NULL_TREE);
1331 arg = tree_cons (NULL, x, arg);
1333 x = implicit_built_in_decls[BUILT_IN_INIT_TRAMPOLINE];
1334 x = build_function_call_expr (x, arg);
1336 append_to_statement_list (x, &stmt_list);
1340 /* If we created initialization statements, insert them. */
1343 annotate_all_with_locus (&stmt_list,
1344 DECL_SOURCE_LOCATION (context));
1345 append_to_statement_list (BIND_EXPR_BODY (DECL_SAVED_TREE (context)),
1347 BIND_EXPR_BODY (DECL_SAVED_TREE (context)) = stmt_list;
1350 /* If a chain_decl was created, then it needs to be registered with
1351 struct function so that it gets initialized from the static chain
1352 register at the beginning of the function. */
1353 sf = DECL_STRUCT_FUNCTION (root->context);
1354 sf->static_chain_decl = root->chain_decl;
1356 /* Similarly for the non-local goto save area. */
1357 if (root->nl_goto_field)
1359 sf->nonlocal_goto_save_area
1360 = get_frame_field (root, context, root->nl_goto_field, NULL);
1361 sf->has_nonlocal_label = 1;
1364 /* Make sure all new local variables get inserted into the
1365 proper BIND_EXPR. */
1366 if (root->new_local_var_chain)
1367 declare_tmp_vars (root->new_local_var_chain,
1368 DECL_SAVED_TREE (root->context));
1370 /* Dump the translated tree function. */
1371 dump_function (TDI_nested, root->context);
1372 node = cgraph_node (root->context);
1374 /* For nested functions update the cgraph to reflect unnesting.
1375 We also delay finalizing of these functions up to this point. */
1378 cgraph_unnest_node (cgraph_node (root->context));
1379 cgraph_finalize_function (root->context, true);
1384 finalize_nesting_tree (struct nesting_info *root)
1389 finalize_nesting_tree (root->inner);
1390 finalize_nesting_tree_1 (root);
1396 /* Free the data structures allocated during this pass. */
1399 free_nesting_tree (struct nesting_info *root)
1401 struct nesting_info *next;
1405 free_nesting_tree (root->inner);
1406 htab_delete (root->var_map);
1414 /* Main entry point for this pass. Process FNDECL and all of its nested
1415 subroutines and turn them into something less tightly bound. */
1418 lower_nested_functions (tree fndecl)
1420 struct nesting_info *root;
1421 struct cgraph_node *cgn;
1423 /* If there are no nested functions, there's nothing to do. */
1424 cgn = cgraph_node (fndecl);
1428 root = create_nesting_tree (cgn);
1429 walk_all_functions (convert_nonlocal_reference, root);
1430 walk_all_functions (convert_local_reference, root);
1431 walk_all_functions (convert_nl_goto_reference, root);
1432 walk_all_functions (convert_nl_goto_receiver, root);
1433 convert_all_function_calls (root);
1434 finalize_nesting_tree (root);
1435 free_nesting_tree (root);
1438 #include "gt-tree-nested.h"