1 /* Nested function decomposition for trees.
2 Copyright (C) 2004, 2005 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 to be used within function CONTEXT.
152 Mark it for addressability as necessary. */
155 build_addr (tree exp, tree context)
161 while (handled_component_p (base))
162 base = TREE_OPERAND (base, 0);
165 TREE_ADDRESSABLE (base) = 1;
167 /* Building the ADDR_EXPR will compute a set of properties for
168 that ADDR_EXPR. Those properties are unfortunately context
169 specific. ie, they are dependent on CURRENT_FUNCTION_DECL.
171 Temporarily set CURRENT_FUNCTION_DECL to the desired context,
172 build the ADDR_EXPR, then restore CURRENT_FUNCTION_DECL. That
173 way the properties are for the ADDR_EXPR are computed properly. */
174 save_context = current_function_decl;
175 current_function_decl = context;
176 retval = build1 (ADDR_EXPR, build_pointer_type (TREE_TYPE (exp)), exp);
177 current_function_decl = save_context;;
181 /* Insert FIELD into TYPE, sorted by alignment requirements. */
184 insert_field_into_struct (tree type, tree field)
188 DECL_CONTEXT (field) = type;
190 for (p = &TYPE_FIELDS (type); *p ; p = &TREE_CHAIN (*p))
191 if (DECL_ALIGN (field) >= DECL_ALIGN (*p))
194 TREE_CHAIN (field) = *p;
198 /* Build or return the RECORD_TYPE that describes the frame state that is
199 shared between INFO->CONTEXT and its nested functions. This record will
200 not be complete until finalize_nesting_tree; up until that point we'll
201 be adding fields as necessary.
203 We also build the DECL that represents this frame in the function. */
206 get_frame_type (struct nesting_info *info)
208 tree type = info->frame_type;
213 type = make_node (RECORD_TYPE);
215 name = concat ("FRAME.",
216 IDENTIFIER_POINTER (DECL_NAME (info->context)),
218 TYPE_NAME (type) = get_identifier (name);
221 info->frame_type = type;
222 info->frame_decl = create_tmp_var_for (info, type, "FRAME");
227 /* Return true if DECL should be referenced by pointer in the non-local
231 use_pointer_in_frame (tree decl)
233 if (TREE_CODE (decl) == PARM_DECL)
235 /* It's illegal to copy TREE_ADDRESSABLE, impossible to copy variable
236 sized decls, and inefficient to copy large aggregates. Don't bother
237 moving anything but scalar variables. */
238 return AGGREGATE_TYPE_P (TREE_TYPE (decl));
242 /* Variable sized types make things "interesting" in the frame. */
243 return DECL_SIZE (decl) == NULL || !TREE_CONSTANT (DECL_SIZE (decl));
247 /* Given DECL, a non-locally accessed variable, find or create a field
248 in the non-local frame structure for the given nesting context. */
251 lookup_field_for_decl (struct nesting_info *info, tree decl,
252 enum insert_option insert)
254 struct var_map_elt *elt, dummy;
259 slot = htab_find_slot (info->var_map, &dummy, insert);
262 gcc_assert (insert != INSERT);
267 if (!elt && insert == INSERT)
269 field = make_node (FIELD_DECL);
270 DECL_NAME (field) = DECL_NAME (decl);
272 if (use_pointer_in_frame (decl))
274 TREE_TYPE (field) = build_pointer_type (TREE_TYPE (decl));
275 DECL_ALIGN (field) = TYPE_ALIGN (TREE_TYPE (field));
276 DECL_NONADDRESSABLE_P (field) = 1;
280 TREE_TYPE (field) = TREE_TYPE (decl);
281 DECL_SOURCE_LOCATION (field) = DECL_SOURCE_LOCATION (decl);
282 DECL_ALIGN (field) = DECL_ALIGN (decl);
283 DECL_USER_ALIGN (field) = DECL_USER_ALIGN (decl);
284 TREE_ADDRESSABLE (field) = TREE_ADDRESSABLE (decl);
285 DECL_NONADDRESSABLE_P (field) = !TREE_ADDRESSABLE (decl);
286 TREE_THIS_VOLATILE (field) = TREE_THIS_VOLATILE (decl);
289 insert_field_into_struct (get_frame_type (info), field);
291 elt = xmalloc (sizeof (*elt));
296 if (TREE_CODE (decl) == PARM_DECL)
297 info->any_parm_remapped = true;
300 field = elt ? elt->new : NULL;
305 /* Build or return the variable that holds the static chain within
306 INFO->CONTEXT. This variable may only be used within INFO->CONTEXT. */
309 get_chain_decl (struct nesting_info *info)
311 tree decl = info->chain_decl;
316 type = get_frame_type (info->outer);
317 type = build_pointer_type (type);
319 /* Note that this variable is *not* entered into any BIND_EXPR;
320 the construction of this variable is handled specially in
321 expand_function_start and initialize_inlined_parameters.
322 Note also that it's represented as a parameter. This is more
323 close to the truth, since the initial value does come from
325 decl = build_decl (PARM_DECL, create_tmp_var_name ("CHAIN"), type);
326 DECL_ARTIFICIAL (decl) = 1;
327 DECL_IGNORED_P (decl) = 1;
328 TREE_USED (decl) = 1;
329 DECL_CONTEXT (decl) = info->context;
330 DECL_ARG_TYPE (decl) = type;
332 /* Tell tree-inline.c that we never write to this variable, so
333 it can copy-prop the replacement value immediately. */
334 TREE_READONLY (decl) = 1;
336 info->chain_decl = decl;
341 /* Build or return the field within the non-local frame state that holds
342 the static chain for INFO->CONTEXT. This is the way to walk back up
343 multiple nesting levels. */
346 get_chain_field (struct nesting_info *info)
348 tree field = info->chain_field;
351 tree type = build_pointer_type (get_frame_type (info->outer));
353 field = make_node (FIELD_DECL);
354 DECL_NAME (field) = get_identifier ("__chain");
355 TREE_TYPE (field) = type;
356 DECL_ALIGN (field) = TYPE_ALIGN (type);
357 DECL_NONADDRESSABLE_P (field) = 1;
359 insert_field_into_struct (get_frame_type (info), field);
361 info->chain_field = field;
366 /* Copy EXP into a temporary. Allocate the temporary in the context of
367 INFO and insert the initialization statement before TSI. */
370 init_tmp_var (struct nesting_info *info, tree exp, tree_stmt_iterator *tsi)
374 t = create_tmp_var_for (info, TREE_TYPE (exp), NULL);
375 stmt = build (MODIFY_EXPR, TREE_TYPE (t), t, exp);
376 SET_EXPR_LOCUS (stmt, EXPR_LOCUS (tsi_stmt (*tsi)));
377 tsi_link_before (tsi, stmt, TSI_SAME_STMT);
382 /* Similarly, but only do so to force EXP to satisfy is_gimple_val. */
385 tsi_gimplify_val (struct nesting_info *info, tree exp, tree_stmt_iterator *tsi)
387 if (is_gimple_val (exp))
390 return init_tmp_var (info, exp, tsi);
393 /* Similarly, but copy from the temporary and insert the statement
394 after the iterator. */
397 save_tmp_var (struct nesting_info *info, tree exp,
398 tree_stmt_iterator *tsi)
402 t = create_tmp_var_for (info, TREE_TYPE (exp), NULL);
403 stmt = build (MODIFY_EXPR, TREE_TYPE (t), exp, t);
404 SET_EXPR_LOCUS (stmt, EXPR_LOCUS (tsi_stmt (*tsi)));
405 tsi_link_after (tsi, stmt, TSI_SAME_STMT);
410 /* Build or return the type used to represent a nested function trampoline. */
412 static GTY(()) tree trampoline_type;
415 get_trampoline_type (void)
418 unsigned align, size;
421 return trampoline_type;
423 align = TRAMPOLINE_ALIGNMENT;
424 size = TRAMPOLINE_SIZE;
426 /* If we won't be able to guarantee alignment simply via TYPE_ALIGN,
427 then allocate extra space so that we can do dynamic alignment. */
428 if (align > STACK_BOUNDARY)
430 size += ((align/BITS_PER_UNIT) - 1) & -(STACK_BOUNDARY/BITS_PER_UNIT);
431 align = STACK_BOUNDARY;
434 t = build_index_type (build_int_cst (NULL_TREE, size - 1));
435 t = build_array_type (char_type_node, t);
436 t = build_decl (FIELD_DECL, get_identifier ("__data"), t);
437 DECL_ALIGN (t) = align;
438 DECL_USER_ALIGN (t) = 1;
440 record = make_node (RECORD_TYPE);
441 TYPE_NAME (record) = get_identifier ("__builtin_trampoline");
442 TYPE_FIELDS (record) = t;
443 layout_type (record);
448 /* Given DECL, a nested function, find or create a field in the non-local
449 frame structure for a trampoline for this function. */
452 lookup_tramp_for_decl (struct nesting_info *info, tree decl,
453 enum insert_option insert)
455 struct var_map_elt *elt, dummy;
460 slot = htab_find_slot (info->var_map, &dummy, insert);
463 gcc_assert (insert != INSERT);
468 if (!elt && insert == INSERT)
470 field = make_node (FIELD_DECL);
471 DECL_NAME (field) = DECL_NAME (decl);
472 TREE_TYPE (field) = get_trampoline_type ();
473 TREE_ADDRESSABLE (field) = 1;
475 insert_field_into_struct (get_frame_type (info), field);
477 elt = xmalloc (sizeof (*elt));
482 info->any_tramp_created = true;
485 field = elt ? elt->new : NULL;
490 /* Build or return the field within the non-local frame state that holds
491 the non-local goto "jmp_buf". The buffer itself is maintained by the
492 rtl middle-end as dynamic stack space is allocated. */
495 get_nl_goto_field (struct nesting_info *info)
497 tree field = info->nl_goto_field;
503 /* For __builtin_nonlocal_goto, we need N words. The first is the
504 frame pointer, the rest is for the target's stack pointer save
505 area. The number of words is controlled by STACK_SAVEAREA_MODE;
506 not the best interface, but it'll do for now. */
507 if (Pmode == ptr_mode)
508 type = ptr_type_node;
510 type = lang_hooks.types.type_for_mode (Pmode, 1);
512 size = GET_MODE_SIZE (STACK_SAVEAREA_MODE (SAVE_NONLOCAL));
513 size = size / GET_MODE_SIZE (Pmode);
516 type = build_array_type
517 (type, build_index_type (build_int_cst (NULL_TREE, size)));
519 field = make_node (FIELD_DECL);
520 DECL_NAME (field) = get_identifier ("__nl_goto_buf");
521 TREE_TYPE (field) = type;
522 DECL_ALIGN (field) = TYPE_ALIGN (type);
523 TREE_ADDRESSABLE (field) = 1;
525 insert_field_into_struct (get_frame_type (info), field);
527 info->nl_goto_field = field;
533 /* Convenience routines to walk all statements of a gimple function.
535 For each statement, we invoke CALLBACK via walk_tree. The passed
536 data is a walk_stmt_info structure. Of note here is a TSI that
537 points to the current statement being walked. The VAL_ONLY flag
538 that indicates whether the *TP being examined may be replaced
539 with something that matches is_gimple_val (if true) or something
540 slightly more complicated (if false). "Something" technically
541 means the common subset of is_gimple_lvalue and is_gimple_rhs,
542 but we never try to form anything more complicated than that, so
543 we don't bother checking. */
545 struct walk_stmt_info
547 walk_tree_fn callback;
548 tree_stmt_iterator tsi;
549 struct nesting_info *info;
555 /* A subroutine of walk_function. Iterate over all sub-statements of *TP. */
558 walk_stmts (struct walk_stmt_info *wi, tree *tp)
564 switch (TREE_CODE (t))
568 tree_stmt_iterator i;
569 for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
572 walk_stmts (wi, tsi_stmt_ptr (i));
578 walk_tree (&COND_EXPR_COND (t), wi->callback, wi, NULL);
579 walk_stmts (wi, &COND_EXPR_THEN (t));
580 walk_stmts (wi, &COND_EXPR_ELSE (t));
583 walk_stmts (wi, &CATCH_BODY (t));
586 walk_stmts (wi, &EH_FILTER_FAILURE (t));
589 case TRY_FINALLY_EXPR:
590 walk_stmts (wi, &TREE_OPERAND (t, 0));
591 walk_stmts (wi, &TREE_OPERAND (t, 1));
594 walk_stmts (wi, &BIND_EXPR_BODY (t));
598 walk_stmts (wi, &TREE_OPERAND (t, 0));
602 /* A formal temporary lhs may use a COMPONENT_REF rhs. */
603 wi->val_only = !is_gimple_formal_tmp_var (TREE_OPERAND (t, 0));
604 walk_tree (&TREE_OPERAND (t, 1), wi->callback, wi, NULL);
606 /* If the rhs is appropriate for a memory, we may use a
607 COMPONENT_REF on the lhs. */
608 wi->val_only = !is_gimple_mem_rhs (TREE_OPERAND (t, 1));
610 walk_tree (&TREE_OPERAND (t, 0), wi->callback, wi, NULL);
618 walk_tree (tp, wi->callback, wi, NULL);
623 /* Invoke CALLBACK on all statements of INFO->CONTEXT. */
626 walk_function (walk_tree_fn callback, struct nesting_info *info)
628 struct walk_stmt_info wi;
630 memset (&wi, 0, sizeof (wi));
631 wi.callback = callback;
635 walk_stmts (&wi, &DECL_SAVED_TREE (info->context));
638 /* Similarly for ROOT and all functions nested underneath, depth first. */
641 walk_all_functions (walk_tree_fn callback, struct nesting_info *root)
646 walk_all_functions (callback, root->inner);
647 walk_function (callback, root);
653 /* We have to check for a fairly pathological case. The operands of function
654 nested function are to be interpreted in the context of the enclosing
655 function. So if any are variably-sized, they will get remapped when the
656 enclosing function is inlined. But that remapping would also have to be
657 done in the types of the PARM_DECLs of the nested function, meaning the
658 argument types of that function will disagree with the arguments in the
659 calls to that function. So we'd either have to make a copy of the nested
660 function corresponding to each time the enclosing function was inlined or
661 add a VIEW_CONVERT_EXPR to each such operand for each call to the nested
662 function. The former is not practical. The latter would still require
663 detecting this case to know when to add the conversions. So, for now at
664 least, we don't inline such an enclosing function.
666 We have to do that check recursively, so here return indicating whether
667 FNDECL has such a nested function. ORIG_FN is the function we were
668 trying to inline to use for checking whether any argument is variably
669 modified by anything in it.
671 It would be better to do this in tree-inline.c so that we could give
672 the appropriate warning for why a function can't be inlined, but that's
673 too late since the nesting structure has already been flattened and
674 adding a flag just to record this fact seems a waste of a flag. */
677 check_for_nested_with_variably_modified (tree fndecl, tree orig_fndecl)
679 struct cgraph_node *cgn = cgraph_node (fndecl);
682 for (cgn = cgn->nested; cgn ; cgn = cgn->next_nested)
684 for (arg = DECL_ARGUMENTS (cgn->decl); arg; arg = TREE_CHAIN (arg))
685 if (variably_modified_type_p (TREE_TYPE (arg), 0), orig_fndecl)
688 if (check_for_nested_with_variably_modified (cgn->decl, orig_fndecl))
695 /* Construct our local datastructure describing the function nesting
696 tree rooted by CGN. */
698 static struct nesting_info *
699 create_nesting_tree (struct cgraph_node *cgn)
701 struct nesting_info *info = xcalloc (1, sizeof (*info));
702 info->var_map = htab_create (7, var_map_hash, var_map_eq, free);
703 info->context = cgn->decl;
705 for (cgn = cgn->nested; cgn ; cgn = cgn->next_nested)
707 struct nesting_info *sub = create_nesting_tree (cgn);
709 sub->next = info->inner;
713 /* See discussion at check_for_nested_with_variably_modified for a
714 discussion of why this has to be here. */
715 if (check_for_nested_with_variably_modified (info->context, info->context))
716 DECL_UNINLINABLE (info->context) = true;
721 /* Return an expression computing the static chain for TARGET_CONTEXT
722 from INFO->CONTEXT. Insert any necessary computations before TSI. */
725 get_static_chain (struct nesting_info *info, tree target_context,
726 tree_stmt_iterator *tsi)
728 struct nesting_info *i;
731 if (info->context == target_context)
733 x = build_addr (info->frame_decl, target_context);
737 x = get_chain_decl (info);
739 for (i = info->outer; i->context != target_context; i = i->outer)
741 tree field = get_chain_field (i);
743 x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
744 x = build (COMPONENT_REF, TREE_TYPE (field), x, field, NULL_TREE);
745 x = init_tmp_var (info, x, tsi);
752 /* Return an expression referencing FIELD from TARGET_CONTEXT's non-local
753 frame as seen from INFO->CONTEXT. Insert any necessary computations
757 get_frame_field (struct nesting_info *info, tree target_context,
758 tree field, tree_stmt_iterator *tsi)
760 struct nesting_info *i;
763 if (info->context == target_context)
765 /* Make sure frame_decl gets created. */
766 (void) get_frame_type (info);
767 x = info->frame_decl;
771 x = get_chain_decl (info);
773 for (i = info->outer; i->context != target_context; i = i->outer)
775 tree field = get_chain_field (i);
777 x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
778 x = build (COMPONENT_REF, TREE_TYPE (field), x, field, NULL_TREE);
779 x = init_tmp_var (info, x, tsi);
782 x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
785 x = build (COMPONENT_REF, TREE_TYPE (field), x, field, NULL_TREE);
789 /* Called via walk_function+walk_tree, rewrite all references to VAR
790 and PARM_DECLs that belong to outer functions.
792 The rewrite will involve some number of structure accesses back up
793 the static chain. E.g. for a variable FOO up one nesting level it'll
794 be CHAIN->FOO. For two levels it'll be CHAIN->__chain->FOO. Further
795 indirections apply to decls for which use_pointer_in_frame is true. */
798 convert_nonlocal_reference (tree *tp, int *walk_subtrees, void *data)
800 struct walk_stmt_info *wi = data;
801 struct nesting_info *info = wi->info;
805 switch (TREE_CODE (t))
808 /* Non-automatic variables are never processed. */
809 if (TREE_STATIC (t) || DECL_EXTERNAL (t))
814 if (decl_function_context (t) != info->context)
816 tree target_context = decl_function_context (t);
817 struct nesting_info *i;
821 for (i = info->outer; i->context != target_context; i = i->outer)
823 x = lookup_field_for_decl (i, t, INSERT);
824 x = get_frame_field (info, target_context, x, &wi->tsi);
825 if (use_pointer_in_frame (t))
827 x = init_tmp_var (info, x, &wi->tsi);
828 x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
834 x = save_tmp_var (info, x, &wi->tsi);
836 x = init_tmp_var (info, x, &wi->tsi);
844 /* Don't walk non-local gotos for now. */
845 if (TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL)
854 /* We're taking the address of a label from a parent function, but
855 this is not itself a non-local goto. Mark the label such that it
856 will not be deleted, much as we would with a label address in
858 if (decl_function_context (t) != info->context)
859 FORCED_LABEL (t) = 1;
864 bool save_val_only = wi->val_only;
866 wi->val_only = false;
869 walk_tree (&TREE_OPERAND (t, 0), convert_nonlocal_reference, wi, NULL);
874 /* If we changed anything, then TREE_INVARIANT is be wrong,
875 since we're no longer directly referencing a decl. */
876 recompute_tree_invarant_for_addr_expr (t);
878 /* If the callback converted the address argument in a context
879 where we only accept variables (and min_invariant, presumably),
880 then compute the address into a temporary. */
882 *tp = tsi_gimplify_val (wi->info, t, &wi->tsi);
891 case ARRAY_RANGE_REF:
893 /* Go down this entire nest and just look at the final prefix and
894 anything that describes the references. Otherwise, we lose track
895 of whether a NOP_EXPR or VIEW_CONVERT_EXPR needs a simple value. */
898 for (; handled_component_p (t); tp = &TREE_OPERAND (t, 0), t = *tp)
900 if (TREE_CODE (t) == COMPONENT_REF)
901 walk_tree (&TREE_OPERAND (t, 2), convert_nonlocal_reference, wi,
903 else if (TREE_CODE (t) == ARRAY_REF
904 || TREE_CODE (t) == ARRAY_RANGE_REF)
906 walk_tree (&TREE_OPERAND (t, 1), convert_nonlocal_reference, wi,
908 walk_tree (&TREE_OPERAND (t, 2), convert_nonlocal_reference, wi,
910 walk_tree (&TREE_OPERAND (t, 3), convert_nonlocal_reference, wi,
913 else if (TREE_CODE (t) == BIT_FIELD_REF)
915 walk_tree (&TREE_OPERAND (t, 1), convert_nonlocal_reference, wi,
917 walk_tree (&TREE_OPERAND (t, 2), convert_nonlocal_reference, wi,
921 wi->val_only = false;
922 walk_tree (tp, convert_nonlocal_reference, wi, NULL);
926 if (!IS_TYPE_OR_DECL_P (t))
938 /* Called via walk_function+walk_tree, rewrite all references to VAR
939 and PARM_DECLs that were referenced by inner nested functions.
940 The rewrite will be a structure reference to the local frame variable. */
943 convert_local_reference (tree *tp, int *walk_subtrees, void *data)
945 struct walk_stmt_info *wi = data;
946 struct nesting_info *info = wi->info;
947 tree t = *tp, field, x;
949 switch (TREE_CODE (t))
952 /* Non-automatic variables are never processed. */
953 if (TREE_STATIC (t) || DECL_EXTERNAL (t))
958 if (decl_function_context (t) == info->context)
960 /* If we copied a pointer to the frame, then the original decl
961 is used unchanged in the parent function. */
962 if (use_pointer_in_frame (t))
965 /* No need to transform anything if no child references the
967 field = lookup_field_for_decl (info, t, NO_INSERT);
972 x = get_frame_field (info, info->context, field, &wi->tsi);
977 x = save_tmp_var (info, x, &wi->tsi);
979 x = init_tmp_var (info, x, &wi->tsi);
988 bool save_val_only = wi->val_only;
990 wi->val_only = false;
993 walk_tree (&TREE_OPERAND (t, 0), convert_local_reference, wi, NULL);
994 wi->val_only = save_val_only;
996 /* If we converted anything ... */
999 /* Then the frame decl is now addressable. */
1000 TREE_ADDRESSABLE (info->frame_decl) = 1;
1002 recompute_tree_invarant_for_addr_expr (t);
1004 /* If we are in a context where we only accept values, then
1005 compute the address into a temporary. */
1007 *tp = tsi_gimplify_val (wi->info, t, &wi->tsi);
1016 case ARRAY_RANGE_REF:
1018 /* Go down this entire nest and just look at the final prefix and
1019 anything that describes the references. Otherwise, we lose track
1020 of whether a NOP_EXPR or VIEW_CONVERT_EXPR needs a simple value. */
1021 wi->val_only = true;
1023 for (; handled_component_p (t); tp = &TREE_OPERAND (t, 0), t = *tp)
1025 if (TREE_CODE (t) == COMPONENT_REF)
1026 walk_tree (&TREE_OPERAND (t, 2), convert_local_reference, wi,
1028 else if (TREE_CODE (t) == ARRAY_REF
1029 || TREE_CODE (t) == ARRAY_RANGE_REF)
1031 walk_tree (&TREE_OPERAND (t, 1), convert_local_reference, wi,
1033 walk_tree (&TREE_OPERAND (t, 2), convert_local_reference, wi,
1035 walk_tree (&TREE_OPERAND (t, 3), convert_local_reference, wi,
1038 else if (TREE_CODE (t) == BIT_FIELD_REF)
1040 walk_tree (&TREE_OPERAND (t, 1), convert_local_reference, wi,
1042 walk_tree (&TREE_OPERAND (t, 2), convert_local_reference, wi,
1046 wi->val_only = false;
1047 walk_tree (tp, convert_local_reference, wi, NULL);
1051 if (!IS_TYPE_OR_DECL_P (t))
1054 wi->val_only = true;
1063 /* Called via walk_function+walk_tree, rewrite all GOTO_EXPRs that
1064 reference labels from outer functions. The rewrite will be a
1065 call to __builtin_nonlocal_goto. */
1068 convert_nl_goto_reference (tree *tp, int *walk_subtrees, void *data)
1070 struct walk_stmt_info *wi = data;
1071 struct nesting_info *info = wi->info, *i;
1072 tree t = *tp, label, new_label, target_context, x, arg, field;
1073 struct var_map_elt *elt;
1077 if (TREE_CODE (t) != GOTO_EXPR)
1079 label = GOTO_DESTINATION (t);
1080 if (TREE_CODE (label) != LABEL_DECL)
1082 target_context = decl_function_context (label);
1083 if (target_context == info->context)
1086 for (i = info->outer; target_context != i->context; i = i->outer)
1089 /* The original user label may also be use for a normal goto, therefore
1090 we must create a new label that will actually receive the abnormal
1091 control transfer. This new label will be marked LABEL_NONLOCAL; this
1092 mark will trigger proper behavior in the cfg, as well as cause the
1093 (hairy target-specific) non-local goto receiver code to be generated
1094 when we expand rtl. */
1095 new_label = create_artificial_label ();
1096 DECL_NONLOCAL (new_label) = 1;
1098 /* Enter this association into var_map so that we can insert the new
1099 label into the IL during a second pass. */
1100 elt = xmalloc (sizeof (*elt));
1102 elt->new = new_label;
1103 slot = htab_find_slot (i->var_map, elt, INSERT);
1106 /* Build: __builtin_nl_goto(new_label, &chain->nl_goto_field). */
1107 field = get_nl_goto_field (i);
1108 x = get_frame_field (info, target_context, field, &wi->tsi);
1109 x = build_addr (x, target_context);
1110 x = tsi_gimplify_val (info, x, &wi->tsi);
1111 arg = tree_cons (NULL, x, NULL);
1112 x = build_addr (new_label, target_context);
1113 arg = tree_cons (NULL, x, arg);
1114 x = implicit_built_in_decls[BUILT_IN_NONLOCAL_GOTO];
1115 x = build_function_call_expr (x, arg);
1117 SET_EXPR_LOCUS (x, EXPR_LOCUS (tsi_stmt (wi->tsi)));
1118 *tsi_stmt_ptr (wi->tsi) = x;
1123 /* Called via walk_function+walk_tree, rewrite all LABEL_EXPRs that
1124 are referenced via nonlocal goto from a nested function. The rewrite
1125 will involve installing a newly generated DECL_NONLOCAL label, and
1126 (potentially) a branch around the rtl gunk that is assumed to be
1127 attached to such a label. */
1130 convert_nl_goto_receiver (tree *tp, int *walk_subtrees, void *data)
1132 struct walk_stmt_info *wi = data;
1133 struct nesting_info *info = wi->info;
1134 tree t = *tp, label, new_label, x;
1135 struct var_map_elt *elt, dummy;
1136 tree_stmt_iterator tmp_tsi;
1139 if (TREE_CODE (t) != LABEL_EXPR)
1141 label = LABEL_EXPR_LABEL (t);
1144 elt = htab_find (info->var_map, &dummy);
1147 new_label = elt->new;
1149 /* If there's any possibility that the previous statement falls through,
1150 then we must branch around the new non-local label. */
1152 tsi_prev (&tmp_tsi);
1153 if (tsi_end_p (tmp_tsi) || block_may_fallthru (tsi_stmt (tmp_tsi)))
1155 x = build1 (GOTO_EXPR, void_type_node, label);
1156 tsi_link_before (&wi->tsi, x, TSI_SAME_STMT);
1158 x = build1 (LABEL_EXPR, void_type_node, new_label);
1159 tsi_link_before (&wi->tsi, x, TSI_SAME_STMT);
1164 /* Called via walk_function+walk_tree, rewrite all references to addresses
1165 of nested functions that require the use of trampolines. The rewrite
1166 will involve a reference a trampoline generated for the occasion. */
1169 convert_tramp_reference (tree *tp, int *walk_subtrees, void *data)
1171 struct walk_stmt_info *wi = data;
1172 struct nesting_info *info = wi->info, *i;
1173 tree t = *tp, decl, target_context, x, arg;
1176 switch (TREE_CODE (t))
1180 T.1 = &CHAIN->tramp;
1181 T.2 = __builtin_adjust_trampoline (T.1);
1182 T.3 = (func_type)T.2;
1185 decl = TREE_OPERAND (t, 0);
1186 if (TREE_CODE (decl) != FUNCTION_DECL)
1189 /* Only need to process nested functions. */
1190 target_context = decl_function_context (decl);
1191 if (!target_context)
1194 /* If the nested function doesn't use a static chain, then
1195 it doesn't need a trampoline. */
1196 if (DECL_NO_STATIC_CHAIN (decl))
1199 /* Lookup the immediate parent of the callee, as that's where
1200 we need to insert the trampoline. */
1201 for (i = info; i->context != target_context; i = i->outer)
1203 x = lookup_tramp_for_decl (i, decl, INSERT);
1205 /* Compute the address of the field holding the trampoline. */
1206 x = get_frame_field (info, target_context, x, &wi->tsi);
1207 x = build_addr (x, target_context);
1208 x = tsi_gimplify_val (info, x, &wi->tsi);
1209 arg = tree_cons (NULL, x, NULL);
1211 /* Do machine-specific ugliness. Normally this will involve
1212 computing extra alignment, but it can really be anything. */
1213 x = implicit_built_in_decls[BUILT_IN_ADJUST_TRAMPOLINE];
1214 x = build_function_call_expr (x, arg);
1215 x = init_tmp_var (info, x, &wi->tsi);
1217 /* Cast back to the proper function type. */
1218 x = build1 (NOP_EXPR, TREE_TYPE (t), x);
1219 x = init_tmp_var (info, x, &wi->tsi);
1225 /* Only walk call arguments, lest we generate trampolines for
1227 walk_tree (&TREE_OPERAND (t, 1), convert_tramp_reference, wi, NULL);
1231 if (!IS_TYPE_OR_DECL_P (t))
1239 /* Called via walk_function+walk_tree, rewrite all CALL_EXPRs that
1240 reference nested functions to make sure that the static chain is
1241 set up properly for the call. */
1244 convert_call_expr (tree *tp, int *walk_subtrees, void *data)
1246 struct walk_stmt_info *wi = data;
1247 struct nesting_info *info = wi->info;
1248 tree t = *tp, decl, target_context;
1251 switch (TREE_CODE (t))
1254 decl = get_callee_fndecl (t);
1257 target_context = decl_function_context (decl);
1258 if (target_context && !DECL_NO_STATIC_CHAIN (decl))
1260 = get_static_chain (info, target_context, &wi->tsi);
1265 case WITH_SIZE_EXPR:
1266 /* Only return modify and with_size_expr may contain calls. */
1277 /* Walk the nesting tree starting with ROOT, depth first. Convert all
1278 trampolines and call expressions. On the way back up, determine if
1279 a nested function actually uses its static chain; if not, remember that. */
1282 convert_all_function_calls (struct nesting_info *root)
1287 convert_all_function_calls (root->inner);
1289 walk_function (convert_tramp_reference, root);
1290 walk_function (convert_call_expr, root);
1292 /* If the function does not use a static chain, then remember that. */
1293 if (root->outer && !root->chain_decl && !root->chain_field)
1294 DECL_NO_STATIC_CHAIN (root->context) = 1;
1296 gcc_assert (!DECL_NO_STATIC_CHAIN (root->context));
1303 /* Do "everything else" to clean up or complete state collected by the
1304 various walking passes -- lay out the types and decls, generate code
1305 to initialize the frame decl, store critical expressions in the
1306 struct function for rtl to find. */
1309 finalize_nesting_tree_1 (struct nesting_info *root)
1311 tree stmt_list = NULL;
1312 tree context = root->context;
1313 struct function *sf;
1314 struct cgraph_node *node;
1316 /* If we created a non-local frame type or decl, we need to lay them
1317 out at this time. */
1318 if (root->frame_type)
1320 layout_type (root->frame_type);
1321 layout_decl (root->frame_decl, 0);
1324 /* If any parameters were referenced non-locally, then we need to
1325 insert a copy. Likewise, if any variables were referenced by
1326 pointer, we need to initialize the address. */
1327 if (root->any_parm_remapped)
1330 for (p = DECL_ARGUMENTS (context); p ; p = TREE_CHAIN (p))
1334 field = lookup_field_for_decl (root, p, NO_INSERT);
1338 if (use_pointer_in_frame (p))
1339 x = build_addr (p, context);
1343 y = build (COMPONENT_REF, TREE_TYPE (field),
1344 root->frame_decl, field, NULL_TREE);
1345 x = build (MODIFY_EXPR, TREE_TYPE (field), y, x);
1346 append_to_statement_list (x, &stmt_list);
1350 /* If a chain_field was created, then it needs to be initialized
1352 if (root->chain_field)
1354 tree x = build (COMPONENT_REF, TREE_TYPE (root->chain_field),
1355 root->frame_decl, root->chain_field, NULL_TREE);
1356 x = build (MODIFY_EXPR, TREE_TYPE (x), x, get_chain_decl (root));
1357 append_to_statement_list (x, &stmt_list);
1360 /* If trampolines were created, then we need to initialize them. */
1361 if (root->any_tramp_created)
1363 struct nesting_info *i;
1364 for (i = root->inner; i ; i = i->next)
1368 field = lookup_tramp_for_decl (root, i->context, NO_INSERT);
1372 if (DECL_NO_STATIC_CHAIN (i->context))
1373 x = null_pointer_node;
1375 x = build_addr (root->frame_decl, context);
1376 arg = tree_cons (NULL, x, NULL);
1378 x = build_addr (i->context, context);
1379 arg = tree_cons (NULL, x, arg);
1381 x = build (COMPONENT_REF, TREE_TYPE (field),
1382 root->frame_decl, field, NULL_TREE);
1383 x = build_addr (x, context);
1384 arg = tree_cons (NULL, x, arg);
1386 x = implicit_built_in_decls[BUILT_IN_INIT_TRAMPOLINE];
1387 x = build_function_call_expr (x, arg);
1389 append_to_statement_list (x, &stmt_list);
1393 /* If we created initialization statements, insert them. */
1396 annotate_all_with_locus (&stmt_list,
1397 DECL_SOURCE_LOCATION (context));
1398 append_to_statement_list (BIND_EXPR_BODY (DECL_SAVED_TREE (context)),
1400 BIND_EXPR_BODY (DECL_SAVED_TREE (context)) = stmt_list;
1403 /* If a chain_decl was created, then it needs to be registered with
1404 struct function so that it gets initialized from the static chain
1405 register at the beginning of the function. */
1406 sf = DECL_STRUCT_FUNCTION (root->context);
1407 sf->static_chain_decl = root->chain_decl;
1409 /* Similarly for the non-local goto save area. */
1410 if (root->nl_goto_field)
1412 sf->nonlocal_goto_save_area
1413 = get_frame_field (root, context, root->nl_goto_field, NULL);
1414 sf->has_nonlocal_label = 1;
1417 /* Make sure all new local variables get inserted into the
1418 proper BIND_EXPR. */
1419 if (root->new_local_var_chain)
1420 declare_tmp_vars (root->new_local_var_chain,
1421 DECL_SAVED_TREE (root->context));
1423 /* Dump the translated tree function. */
1424 dump_function (TDI_nested, root->context);
1425 node = cgraph_node (root->context);
1427 /* For nested functions update the cgraph to reflect unnesting.
1428 We also delay finalizing of these functions up to this point. */
1431 cgraph_unnest_node (cgraph_node (root->context));
1432 cgraph_finalize_function (root->context, true);
1437 finalize_nesting_tree (struct nesting_info *root)
1442 finalize_nesting_tree (root->inner);
1443 finalize_nesting_tree_1 (root);
1449 /* Free the data structures allocated during this pass. */
1452 free_nesting_tree (struct nesting_info *root)
1454 struct nesting_info *next;
1458 free_nesting_tree (root->inner);
1459 htab_delete (root->var_map);
1467 /* Main entry point for this pass. Process FNDECL and all of its nested
1468 subroutines and turn them into something less tightly bound. */
1471 lower_nested_functions (tree fndecl)
1473 struct nesting_info *root;
1474 struct cgraph_node *cgn;
1476 /* If there are no nested functions, there's nothing to do. */
1477 cgn = cgraph_node (fndecl);
1481 root = create_nesting_tree (cgn);
1482 walk_all_functions (convert_nonlocal_reference, root);
1483 walk_all_functions (convert_local_reference, root);
1484 walk_all_functions (convert_nl_goto_reference, root);
1485 walk_all_functions (convert_nl_goto_receiver, root);
1486 convert_all_function_calls (root);
1487 finalize_nesting_tree (root);
1488 free_nesting_tree (root);
1491 #include "gt-tree-nested.h"