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 incomming
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 defined ENABLE_CHECKING
136 /* If the type is an array or a type which must be created by the
137 frontend, something is wrong. Note that we explicitly allow
138 incomplete types here, since we create them ourselves here. */
139 if (TREE_CODE (type) == ARRAY_TYPE || TREE_ADDRESSABLE (type))
141 if (TYPE_SIZE_UNIT (type)
142 && TREE_CODE (TYPE_SIZE_UNIT (type)) != INTEGER_CST)
146 tmp_var = create_tmp_var_raw (type, prefix);
147 DECL_CONTEXT (tmp_var) = info->context;
148 TREE_CHAIN (tmp_var) = info->new_local_var_chain;
149 info->new_local_var_chain = tmp_var;
154 /* Take the address of EXP. Mark it for addressability as necessary. */
157 build_addr (tree exp)
161 if (TREE_CODE (base) == REALPART_EXPR || TREE_CODE (base) == IMAGPART_EXPR)
162 base = TREE_OPERAND (base, 0);
164 while (handled_component_p (base))
165 base = TREE_OPERAND (base, 0);
168 TREE_ADDRESSABLE (base) = 1;
170 return build1 (ADDR_EXPR, build_pointer_type (TREE_TYPE (exp)), exp);
173 /* Insert FIELD into TYPE, sorted by alignment requirements. */
176 insert_field_into_struct (tree type, tree field)
180 DECL_CONTEXT (field) = type;
182 for (p = &TYPE_FIELDS (type); *p ; p = &TREE_CHAIN (*p))
183 if (DECL_ALIGN (field) >= DECL_ALIGN (*p))
186 TREE_CHAIN (field) = *p;
190 /* Build or return the RECORD_TYPE that describes the frame state that is
191 shared between INFO->CONTEXT and its nested functions. This record will
192 not be complete until finalize_nesting_tree; up until that point we'll
193 be adding fields as necessary.
195 We also build the DECL that represents this frame in the function. */
198 get_frame_type (struct nesting_info *info)
200 tree type = info->frame_type;
205 type = make_node (RECORD_TYPE);
207 name = concat ("FRAME.",
208 IDENTIFIER_POINTER (DECL_NAME (info->context)),
210 TYPE_NAME (type) = get_identifier (name);
213 info->frame_type = type;
214 info->frame_decl = create_tmp_var_for (info, type, "FRAME");
219 /* Return true if DECL should be referenced by pointer in the non-local
223 use_pointer_in_frame (tree decl)
225 if (TREE_CODE (decl) == PARM_DECL)
227 /* It's illegal to copy TREE_ADDRESSABLE, impossible to copy variable
228 sized decls, and inefficient to copy large aggregates. Don't bother
229 moving anything but scalar variables. */
230 return AGGREGATE_TYPE_P (TREE_TYPE (decl));
234 /* Variable sized types make things "interesting" in the frame. */
235 return DECL_SIZE (decl) == NULL || !TREE_CONSTANT (DECL_SIZE (decl));
239 /* Given DECL, a non-locally accessed variable, find or create a field
240 in the non-local frame structure for the given nesting context. */
243 lookup_field_for_decl (struct nesting_info *info, tree decl,
244 enum insert_option insert)
246 struct var_map_elt *elt, dummy;
251 slot = htab_find_slot (info->var_map, &dummy, insert);
254 if (insert == INSERT)
260 if (!elt && insert == INSERT)
262 field = make_node (FIELD_DECL);
263 DECL_NAME (field) = DECL_NAME (decl);
265 if (use_pointer_in_frame (decl))
267 TREE_TYPE (field) = build_pointer_type (TREE_TYPE (decl));
268 DECL_ALIGN (field) = TYPE_ALIGN (TREE_TYPE (field));
269 DECL_NONADDRESSABLE_P (field) = 1;
273 TREE_TYPE (field) = TREE_TYPE (decl);
274 DECL_SOURCE_LOCATION (field) = DECL_SOURCE_LOCATION (decl);
275 DECL_ALIGN (field) = DECL_ALIGN (decl);
276 DECL_USER_ALIGN (field) = DECL_USER_ALIGN (decl);
277 TREE_ADDRESSABLE (field) = TREE_ADDRESSABLE (decl);
278 DECL_NONADDRESSABLE_P (field) = !TREE_ADDRESSABLE (decl);
279 TREE_THIS_VOLATILE (field) = TREE_THIS_VOLATILE (decl);
282 insert_field_into_struct (get_frame_type (info), field);
284 elt = xmalloc (sizeof (*elt));
289 if (TREE_CODE (decl) == PARM_DECL)
290 info->any_parm_remapped = true;
293 field = elt ? elt->new : NULL;
298 /* Build or return the variable that holds the static chain within
299 INFO->CONTEXT. This variable may only be used within INFO->CONTEXT. */
302 get_chain_decl (struct nesting_info *info)
304 tree decl = info->chain_decl;
309 type = get_frame_type (info->outer);
310 type = build_pointer_type (type);
312 /* Note that this variable is *not* entered into any BIND_EXPR;
313 the construction of this variable is handled specially in
314 expand_function_start and initialize_inlined_parameters.
315 Note also that it's represented as a parameter. This is more
316 close to the truth, since the initial value does come from
318 decl = build_decl (PARM_DECL, create_tmp_var_name ("CHAIN"), type);
319 DECL_ARTIFICIAL (decl) = 1;
320 DECL_IGNORED_P (decl) = 1;
321 TREE_USED (decl) = 1;
322 DECL_CONTEXT (decl) = info->context;
323 DECL_ARG_TYPE (decl) = type;
325 /* Tell tree-inline.c that we never write to this variable, so
326 it can copy-prop the replacement value immediately. */
327 TREE_READONLY (decl) = 1;
329 info->chain_decl = decl;
334 /* Build or return the field within the non-local frame state that holds
335 the static chain for INFO->CONTEXT. This is the way to walk back up
336 multiple nesting levels. */
339 get_chain_field (struct nesting_info *info)
341 tree field = info->chain_field;
344 tree type = build_pointer_type (get_frame_type (info->outer));
346 field = make_node (FIELD_DECL);
347 DECL_NAME (field) = get_identifier ("__chain");
348 TREE_TYPE (field) = type;
349 DECL_ALIGN (field) = TYPE_ALIGN (type);
350 DECL_NONADDRESSABLE_P (field) = 1;
352 insert_field_into_struct (get_frame_type (info), field);
354 info->chain_field = field;
359 /* Copy EXP into a temporary. Allocate the temporary in the context of
360 INFO and insert the initialization statement before TSI. */
363 init_tmp_var (struct nesting_info *info, tree exp, tree_stmt_iterator *tsi)
367 t = create_tmp_var_for (info, TREE_TYPE (exp), NULL);
368 stmt = build (MODIFY_EXPR, TREE_TYPE (t), t, exp);
369 SET_EXPR_LOCUS (stmt, EXPR_LOCUS (tsi_stmt (*tsi)));
370 tsi_link_before (tsi, stmt, TSI_SAME_STMT);
375 /* Similarly, but only do so to force EXP to satisfy is_gimple_val. */
378 gimplify_val (struct nesting_info *info, tree exp, tree_stmt_iterator *tsi)
380 if (is_gimple_val (exp))
383 return init_tmp_var (info, exp, tsi);
386 /* Build or return the type used to represent a nested function trampoline. */
388 static GTY(()) tree trampoline_type;
391 get_trampoline_type (void)
394 unsigned align, size;
397 return trampoline_type;
399 align = TRAMPOLINE_ALIGNMENT;
400 size = TRAMPOLINE_SIZE;
402 /* If we won't be able to guarantee alignment simply via TYPE_ALIGN,
403 then allocate extra space so that we can do dynamic alignment. */
404 if (align > STACK_BOUNDARY)
406 size += ((align/BITS_PER_UNIT) - 1) & -(STACK_BOUNDARY/BITS_PER_UNIT);
407 align = STACK_BOUNDARY;
410 t = build_index_type (build_int_2 (size - 1, 0));
411 t = build_array_type (char_type_node, t);
412 t = build_decl (FIELD_DECL, get_identifier ("__data"), t);
413 DECL_ALIGN (t) = align;
414 DECL_USER_ALIGN (t) = 1;
416 record = make_node (RECORD_TYPE);
417 TYPE_NAME (record) = get_identifier ("__builtin_trampoline");
418 TYPE_FIELDS (record) = t;
419 layout_type (record);
424 /* Given DECL, a nested function, find or create a field in the non-local
425 frame structure for a trampoline for this function. */
428 lookup_tramp_for_decl (struct nesting_info *info, tree decl,
429 enum insert_option insert)
431 struct var_map_elt *elt, dummy;
436 slot = htab_find_slot (info->var_map, &dummy, insert);
439 if (insert == INSERT)
445 if (!elt && insert == INSERT)
447 field = make_node (FIELD_DECL);
448 DECL_NAME (field) = DECL_NAME (decl);
449 TREE_TYPE (field) = get_trampoline_type ();
450 TREE_ADDRESSABLE (field) = 1;
452 insert_field_into_struct (get_frame_type (info), field);
454 elt = xmalloc (sizeof (*elt));
459 info->any_tramp_created = true;
462 field = elt ? elt->new : NULL;
467 /* Build or return the field within the non-local frame state that holds
468 the non-local goto "jmp_buf". The buffer itself is maintained by the
469 rtl middle-end as dynamic stack space is allocated. */
472 get_nl_goto_field (struct nesting_info *info)
474 tree field = info->nl_goto_field;
480 /* For __builtin_nonlocal_goto, we need N words. The first is the
481 frame pointer, the rest is for the target's stack pointer save
482 area. The number of words is controlled by STACK_SAVEAREA_MODE;
483 not the best interface, but it'll do for now. */
484 if (Pmode == ptr_mode)
485 type = ptr_type_node;
487 type = lang_hooks.types.type_for_mode (Pmode, 1);
489 size = GET_MODE_SIZE (STACK_SAVEAREA_MODE (SAVE_NONLOCAL));
490 size = size / GET_MODE_SIZE (Pmode);
493 type = build_array_type (type, build_index_type (build_int_2 (size, 0)));
495 field = make_node (FIELD_DECL);
496 DECL_NAME (field) = get_identifier ("__nl_goto_buf");
497 TREE_TYPE (field) = type;
498 DECL_ALIGN (field) = TYPE_ALIGN (type);
499 TREE_ADDRESSABLE (field) = 1;
501 insert_field_into_struct (get_frame_type (info), field);
503 info->nl_goto_field = field;
509 /* Convenience routines to walk all statements of a gimple function.
511 For each statement, we invoke CALLBACK via walk_tree. The passed
512 data is a walk_stmt_info structure. Of note here is a TSI that
513 points to the current statement being walked. The VAL_ONLY flag
514 that indicates whether the *TP being examined may be replaced
515 with something that matches is_gimple_val (if true) or something
516 slightly more complicated (if false). "Something" technically
517 means the common subset of is_gimple_lvalue and is_gimple_rhs,
518 but we never try to form anything more complicated than that, so
519 we don't bother checking. */
521 struct walk_stmt_info
523 walk_tree_fn callback;
524 tree_stmt_iterator tsi;
525 struct nesting_info *info;
529 /* A subroutine of walk_function. Iterate over all sub-statements of *TP. */
532 walk_stmts (struct walk_stmt_info *wi, tree *tp)
538 switch (TREE_CODE (t))
542 tree_stmt_iterator i;
543 for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
546 walk_stmts (wi, tsi_stmt_ptr (i));
552 walk_tree (&COND_EXPR_COND (t), wi->callback, wi, NULL);
553 walk_stmts (wi, &COND_EXPR_THEN (t));
554 walk_stmts (wi, &COND_EXPR_ELSE (t));
557 walk_stmts (wi, &CATCH_BODY (t));
560 walk_stmts (wi, &EH_FILTER_FAILURE (t));
563 case TRY_FINALLY_EXPR:
564 walk_stmts (wi, &TREE_OPERAND (t, 0));
565 walk_stmts (wi, &TREE_OPERAND (t, 1));
568 walk_stmts (wi, &BIND_EXPR_BODY (t));
572 walk_stmts (wi, &TREE_OPERAND (t, 0));
576 /* The immediate arguments of a MODIFY_EXPR may use COMPONENT_REF. */
577 wi->val_only = false;
578 walk_tree (&TREE_OPERAND (t, 0), wi->callback, wi, NULL);
579 wi->val_only = false;
580 walk_tree (&TREE_OPERAND (t, 1), wi->callback, wi, NULL);
586 walk_tree (tp, wi->callback, wi, NULL);
591 /* Invoke CALLBACK on all statements of INFO->CONTEXT. */
594 walk_function (walk_tree_fn callback, struct nesting_info *info)
596 struct walk_stmt_info wi;
598 memset (&wi, 0, sizeof (wi));
599 wi.callback = callback;
603 walk_stmts (&wi, &DECL_SAVED_TREE (info->context));
606 /* Similarly for ROOT and all functions nested underneath, depth first. */
609 walk_all_functions (walk_tree_fn callback, struct nesting_info *root)
614 walk_all_functions (callback, root->inner);
615 walk_function (callback, root);
622 /* Construct our local datastructure describing the function nesting
623 tree rooted by CGN. */
625 static struct nesting_info *
626 create_nesting_tree (struct cgraph_node *cgn)
628 struct nesting_info *info = xcalloc (1, sizeof (*info));
629 info->var_map = htab_create (7, var_map_hash, var_map_eq, free);
630 info->context = cgn->decl;
632 for (cgn = cgn->nested; cgn ; cgn = cgn->next_nested)
634 struct nesting_info *sub = create_nesting_tree (cgn);
636 sub->next = info->inner;
643 /* Return an expression computing the static chain for TARGET_CONTEXT
644 from INFO->CONTEXT. Insert any necessary computations before TSI. */
647 get_static_chain (struct nesting_info *info, tree target_context,
648 tree_stmt_iterator *tsi)
650 struct nesting_info *i;
653 if (info->context == target_context)
655 x = build_addr (info->frame_decl);
659 x = get_chain_decl (info);
661 for (i = info->outer; i->context != target_context; i = i->outer)
663 tree field = get_chain_field (i);
665 x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
666 x = build (COMPONENT_REF, TREE_TYPE (field), x, field, NULL_TREE);
667 x = init_tmp_var (info, x, tsi);
674 /* Return an expression referencing FIELD from TARGET_CONTEXT's non-local
675 frame as seen from INFO->CONTEXT. Insert any necessary computations
679 get_frame_field (struct nesting_info *info, tree target_context,
680 tree field, tree_stmt_iterator *tsi)
682 struct nesting_info *i;
685 if (info->context == target_context)
687 /* Make sure frame_decl gets created. */
688 (void) get_frame_type (info);
689 x = info->frame_decl;
693 x = get_chain_decl (info);
695 for (i = info->outer; i->context != target_context; i = i->outer)
697 tree field = get_chain_field (i);
699 x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
700 x = build (COMPONENT_REF, TREE_TYPE (field), x, field, NULL_TREE);
701 x = init_tmp_var (info, x, tsi);
704 x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
707 x = build (COMPONENT_REF, TREE_TYPE (field), x, field, NULL_TREE);
711 /* Called via walk_function+walk_tree, rewrite all references to VAR
712 and PARM_DECLs that belong to outer functions.
714 The rewrite will involve some number of structure accesses back up
715 the static chain. E.g. for a variable FOO up one nesting level it'll
716 be CHAIN->FOO. For two levels it'll be CHAIN->__chain->FOO. Further
717 indirections apply to decls for which use_pointer_in_frame is true. */
720 convert_nonlocal_reference (tree *tp, int *walk_subtrees, void *data)
722 struct walk_stmt_info *wi = data;
723 struct nesting_info *info = wi->info;
727 switch (TREE_CODE (t))
730 /* Non-automatic variables are never processed. */
731 if (TREE_STATIC (t) || DECL_EXTERNAL (t))
736 if (decl_function_context (t) != info->context)
738 tree target_context = decl_function_context (t);
739 struct nesting_info *i;
742 for (i = info->outer; i->context != target_context; i = i->outer)
744 x = lookup_field_for_decl (i, t, INSERT);
745 x = get_frame_field (info, target_context, x, &wi->tsi);
746 if (use_pointer_in_frame (t))
748 x = init_tmp_var (info, x, &wi->tsi);
749 x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
752 x = init_tmp_var (info, x, &wi->tsi);
759 /* Don't walk non-local gotos for now. */
760 if (TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL)
768 /* We're taking the address of a label from a parent function, but
769 this is not itself a non-local goto. Mark the label such that it
770 will not be deleted, much as we would with a label address in
772 if (decl_function_context (t) != info->context)
773 FORCED_LABEL (t) = 1;
778 bool save_val_only = wi->val_only;
779 tree save_sub = TREE_OPERAND (t, 0);
781 wi->val_only = false;
782 walk_tree (&TREE_OPERAND (t, 0), convert_nonlocal_reference, wi, NULL);
785 if (save_sub != TREE_OPERAND (t, 0))
787 /* If we changed anything, then TREE_INVARIANT is be wrong,
788 since we're no longer directly referencing a decl. */
789 TREE_INVARIANT (t) = 0;
791 /* If the callback converted the address argument in a context
792 where we only accept variables (and min_invariant, presumably),
793 then compute the address into a temporary. */
795 *tp = gimplify_val (wi->info, t, &wi->tsi);
803 wi->val_only = false;
804 walk_tree (&TREE_OPERAND (t, 0), convert_nonlocal_reference, wi, NULL);
809 case ARRAY_RANGE_REF:
810 wi->val_only = false;
811 walk_tree (&TREE_OPERAND (t, 0), convert_nonlocal_reference, wi, NULL);
813 walk_tree (&TREE_OPERAND (t, 1), convert_nonlocal_reference, wi, NULL);
814 walk_tree (&TREE_OPERAND (t, 2), convert_nonlocal_reference, wi, NULL);
815 walk_tree (&TREE_OPERAND (t, 3), convert_nonlocal_reference, wi, NULL);
819 wi->val_only = false;
820 walk_tree (&TREE_OPERAND (t, 0), convert_nonlocal_reference, wi, NULL);
822 walk_tree (&TREE_OPERAND (t, 1), convert_nonlocal_reference, wi, NULL);
823 walk_tree (&TREE_OPERAND (t, 2), convert_nonlocal_reference, wi, NULL);
827 if (!DECL_P (t) && !TYPE_P (t))
838 /* Called via walk_function+walk_tree, rewrite all references to VAR
839 and PARM_DECLs that were referenced by inner nested functions.
840 The rewrite will be a structure reference to the local frame variable. */
843 convert_local_reference (tree *tp, int *walk_subtrees, void *data)
845 struct walk_stmt_info *wi = data;
846 struct nesting_info *info = wi->info;
847 tree t = *tp, field, x, y;
849 switch (TREE_CODE (t))
852 /* Non-automatic variables are never processed. */
853 if (TREE_STATIC (t) || DECL_EXTERNAL (t))
858 if (decl_function_context (t) == info->context)
860 /* If we copied a pointer to the frame, then the original decl
861 is used unchanged in the parent function. */
862 if (use_pointer_in_frame (t))
865 /* No need to transform anything if no child references the
867 field = lookup_field_for_decl (info, t, NO_INSERT);
871 x = get_frame_field (info, info->context, field, &wi->tsi);
873 x = init_tmp_var (info, x, &wi->tsi);
880 bool save_val_only = wi->val_only;
881 tree save_sub = TREE_OPERAND (t, 0);
883 wi->val_only = false;
884 walk_tree (&TREE_OPERAND (t, 0), convert_local_reference, wi, NULL);
885 wi->val_only = save_val_only;
887 /* If we converted anything ... */
888 if (TREE_OPERAND (t, 0) != save_sub)
890 /* Then the frame decl is now addressable. */
891 TREE_ADDRESSABLE (info->frame_decl) = 1;
893 /* If we are in a context where we only accept values, then
894 compute the address into a temporary. */
896 *tp = gimplify_val (wi->info, t, &wi->tsi);
904 /* Ready for some fun? We need to recognize
905 __builtin_stack_alloc (&x, n)
908 after that. X should have use_pointer_in_frame set. We can't
909 do this any earlier, since we can't meaningfully evaluate &x. */
911 x = get_callee_fndecl (t);
912 if (!x || DECL_BUILT_IN_CLASS (x) != BUILT_IN_NORMAL)
914 if (DECL_FUNCTION_CODE (x) != BUILT_IN_STACK_ALLOC)
916 t = TREE_VALUE (TREE_OPERAND (t, 1));
917 if (TREE_CODE (t) != ADDR_EXPR)
919 t = TREE_OPERAND (t, 0);
920 if (TREE_CODE (t) != VAR_DECL)
922 field = lookup_field_for_decl (info, t, NO_INSERT);
925 if (!use_pointer_in_frame (t))
929 y = get_frame_field (info, info->context, field, &wi->tsi);
930 x = build (MODIFY_EXPR, void_type_node, y, x);
931 SET_EXPR_LOCUS (x, EXPR_LOCUS (tsi_stmt (wi->tsi)));
932 tsi_link_after (&wi->tsi, x, TSI_SAME_STMT);
938 wi->val_only = false;
939 walk_tree (&TREE_OPERAND (t, 0), convert_local_reference, wi, NULL);
944 case ARRAY_RANGE_REF:
945 wi->val_only = false;
946 walk_tree (&TREE_OPERAND (t, 0), convert_local_reference, wi, NULL);
948 walk_tree (&TREE_OPERAND (t, 1), convert_local_reference, wi, NULL);
949 walk_tree (&TREE_OPERAND (t, 2), convert_local_reference, wi, NULL);
950 walk_tree (&TREE_OPERAND (t, 3), convert_local_reference, wi, NULL);
954 wi->val_only = false;
955 walk_tree (&TREE_OPERAND (t, 0), convert_local_reference, wi, NULL);
957 walk_tree (&TREE_OPERAND (t, 1), convert_local_reference, wi, NULL);
958 walk_tree (&TREE_OPERAND (t, 2), convert_local_reference, wi, NULL);
962 if (!DECL_P (t) && !TYPE_P (t))
973 /* Called via walk_function+walk_tree, rewrite all GOTO_EXPRs that
974 reference labels from outer functions. The rewrite will be a
975 call to __builtin_nonlocal_goto. */
978 convert_nl_goto_reference (tree *tp, int *walk_subtrees, void *data)
980 struct walk_stmt_info *wi = data;
981 struct nesting_info *info = wi->info, *i;
982 tree t = *tp, label, new_label, target_context, x, arg, field;
983 struct var_map_elt *elt;
987 if (TREE_CODE (t) != GOTO_EXPR)
989 label = GOTO_DESTINATION (t);
990 if (TREE_CODE (label) != LABEL_DECL)
992 target_context = decl_function_context (label);
993 if (target_context == info->context)
996 for (i = info->outer; target_context != i->context; i = i->outer)
999 /* The original user label may also be use for a normal goto, therefore
1000 we must create a new label that will actually receive the abnormal
1001 control transfer. This new label will be marked LABEL_NONLOCAL; this
1002 mark will trigger proper behavior in the cfg, as well as cause the
1003 (hairy target-specific) non-local goto receiver code to be generated
1004 when we expand rtl. */
1005 new_label = create_artificial_label ();
1006 DECL_NONLOCAL (new_label) = 1;
1008 /* Enter this association into var_map so that we can insert the new
1009 label into the IL during a second pass. */
1010 elt = xmalloc (sizeof (*elt));
1012 elt->new = new_label;
1013 slot = htab_find_slot (i->var_map, elt, INSERT);
1016 /* Build: __builtin_nl_goto(new_label, &chain->nl_goto_field). */
1017 field = get_nl_goto_field (i);
1018 x = get_frame_field (info, target_context, field, &wi->tsi);
1020 x = gimplify_val (info, x, &wi->tsi);
1021 arg = tree_cons (NULL, x, NULL);
1022 x = build_addr (new_label);
1023 arg = tree_cons (NULL, x, arg);
1024 x = implicit_built_in_decls[BUILT_IN_NONLOCAL_GOTO];
1025 x = build_function_call_expr (x, arg);
1027 SET_EXPR_LOCUS (x, EXPR_LOCUS (tsi_stmt (wi->tsi)));
1028 *tsi_stmt_ptr (wi->tsi) = x;
1033 /* Called via walk_function+walk_tree, rewrite all LABEL_EXPRs that
1034 are referenced via nonlocal goto from a nested function. The rewrite
1035 will involve installing a newly generated DECL_NONLOCAL label, and
1036 (potentially) a branch around the rtl gunk that is assumed to be
1037 attached to such a label. */
1040 convert_nl_goto_receiver (tree *tp, int *walk_subtrees, void *data)
1042 struct walk_stmt_info *wi = data;
1043 struct nesting_info *info = wi->info;
1044 tree t = *tp, label, new_label, x;
1045 struct var_map_elt *elt, dummy;
1046 tree_stmt_iterator tmp_tsi;
1049 if (TREE_CODE (t) != LABEL_EXPR)
1051 label = LABEL_EXPR_LABEL (t);
1054 elt = htab_find (info->var_map, &dummy);
1057 new_label = elt->new;
1059 /* If there's any possibility that the previous statement falls through,
1060 then we must branch around the new non-local label. */
1062 tsi_prev (&tmp_tsi);
1063 if (tsi_end_p (tmp_tsi) || block_may_fallthru (tsi_stmt (tmp_tsi)))
1065 x = build1 (GOTO_EXPR, void_type_node, label);
1066 tsi_link_before (&wi->tsi, x, TSI_SAME_STMT);
1068 x = build1 (LABEL_EXPR, void_type_node, new_label);
1069 tsi_link_before (&wi->tsi, x, TSI_SAME_STMT);
1074 /* Called via walk_function+walk_tree, rewrite all references to addresses
1075 of nested functions that require the use of trampolines. The rewrite
1076 will involve a reference a trampoline generated for the occasion. */
1079 convert_tramp_reference (tree *tp, int *walk_subtrees, void *data)
1081 struct walk_stmt_info *wi = data;
1082 struct nesting_info *info = wi->info, *i;
1083 tree t = *tp, decl, target_context, x, arg;
1086 switch (TREE_CODE (t))
1090 T.1 = &CHAIN->tramp;
1091 T.2 = __builtin_adjust_trampoline (T.1);
1092 T.3 = (func_type)T.2;
1095 decl = TREE_OPERAND (t, 0);
1096 if (TREE_CODE (decl) != FUNCTION_DECL)
1099 /* Only need to process nested functions. */
1100 target_context = decl_function_context (decl);
1101 if (!target_context)
1104 /* If the nested function doesn't use a static chain, then
1105 it doesn't need a trampoline. */
1106 if (DECL_NO_STATIC_CHAIN (decl))
1109 /* Lookup the immediate parent of the callee, as that's where
1110 we need to insert the trampoline. */
1111 for (i = info; i->context != target_context; i = i->outer)
1113 x = lookup_tramp_for_decl (i, decl, INSERT);
1115 /* Compute the address of the field holding the trampoline. */
1116 x = get_frame_field (info, target_context, x, &wi->tsi);
1118 x = gimplify_val (info, x, &wi->tsi);
1119 arg = tree_cons (NULL, x, NULL);
1121 /* Do machine-specific ugliness. Normally this will involve
1122 computing extra alignment, but it can really be anything. */
1123 x = implicit_built_in_decls[BUILT_IN_ADJUST_TRAMPOLINE];
1124 x = build_function_call_expr (x, arg);
1125 x = init_tmp_var (info, x, &wi->tsi);
1127 /* Cast back to the proper function type. */
1128 x = build1 (NOP_EXPR, TREE_TYPE (t), x);
1129 x = init_tmp_var (info, x, &wi->tsi);
1135 /* Only walk call arguments, lest we generate trampolines for
1137 walk_tree (&TREE_OPERAND (t, 1), convert_tramp_reference, wi, NULL);
1141 if (!DECL_P (t) && !TYPE_P (t))
1149 /* Called via walk_function+walk_tree, rewrite all CALL_EXPRs that
1150 reference nested functions to make sure that the static chain is
1151 set up properly for the call. */
1154 convert_call_expr (tree *tp, int *walk_subtrees, void *data)
1156 struct walk_stmt_info *wi = data;
1157 struct nesting_info *info = wi->info;
1158 tree t = *tp, decl, target_context;
1161 switch (TREE_CODE (t))
1164 decl = get_callee_fndecl (t);
1167 target_context = decl_function_context (decl);
1168 if (target_context && !DECL_NO_STATIC_CHAIN (decl))
1170 = get_static_chain (info, target_context, &wi->tsi);
1175 /* Only return and modify may contain calls. */
1186 /* Walk the nesting tree starting with ROOT, depth first. Convert all
1187 trampolines and call expressions. On the way back up, determine if
1188 a nested function actually uses its static chain; if not, remember that. */
1191 convert_all_function_calls (struct nesting_info *root)
1196 convert_all_function_calls (root->inner);
1198 walk_function (convert_tramp_reference, root);
1199 walk_function (convert_call_expr, root);
1201 /* If the function does not use a static chain, then remember that. */
1202 if (root->outer && !root->chain_decl && !root->chain_field)
1203 DECL_NO_STATIC_CHAIN (root->context) = 1;
1206 #ifdef ENABLE_CHECKING
1207 if (DECL_NO_STATIC_CHAIN (root->context))
1217 /* Do "everything else" to clean up or complete state collected by the
1218 various walking passes -- lay out the types and decls, generate code
1219 to initialize the frame decl, store critical expressions in the
1220 struct function for rtl to find. */
1223 finalize_nesting_tree_1 (struct nesting_info *root)
1225 tree stmt_list = NULL;
1226 tree context = root->context;
1227 struct function *sf;
1229 /* If we created a non-local frame type or decl, we need to lay them
1230 out at this time. */
1231 if (root->frame_type)
1233 layout_type (root->frame_type);
1234 layout_decl (root->frame_decl, 0);
1237 /* If any parameters were referenced non-locally, then we need to
1238 insert a copy. Likewise, if any variables were referenced by
1239 pointer, we need to initialize the address. */
1240 if (root->any_parm_remapped)
1243 for (p = DECL_ARGUMENTS (context); p ; p = TREE_CHAIN (p))
1247 field = lookup_field_for_decl (root, p, NO_INSERT);
1251 if (use_pointer_in_frame (p))
1256 y = build (COMPONENT_REF, TREE_TYPE (field),
1257 root->frame_decl, field, NULL_TREE);
1258 x = build (MODIFY_EXPR, TREE_TYPE (field), y, x);
1259 append_to_statement_list (x, &stmt_list);
1263 /* If a chain_field was created, then it needs to be initialized
1265 if (root->chain_field)
1267 tree x = build (COMPONENT_REF, TREE_TYPE (root->chain_field),
1268 root->frame_decl, root->chain_field, NULL_TREE);
1269 x = build (MODIFY_EXPR, TREE_TYPE (x), x, get_chain_decl (root));
1270 append_to_statement_list (x, &stmt_list);
1273 /* If trampolines were created, then we need to initialize them. */
1274 if (root->any_tramp_created)
1276 struct nesting_info *i;
1277 for (i = root->inner; i ; i = i->next)
1281 field = lookup_tramp_for_decl (root, i->context, NO_INSERT);
1285 if (DECL_NO_STATIC_CHAIN (i->context))
1286 x = null_pointer_node;
1288 x = build_addr (root->frame_decl);
1289 arg = tree_cons (NULL, x, NULL);
1291 x = build_addr (i->context);
1292 arg = tree_cons (NULL, x, arg);
1294 x = build (COMPONENT_REF, TREE_TYPE (field),
1295 root->frame_decl, field, NULL_TREE);
1297 arg = tree_cons (NULL, x, arg);
1299 x = implicit_built_in_decls[BUILT_IN_INIT_TRAMPOLINE];
1300 x = build_function_call_expr (x, arg);
1302 append_to_statement_list (x, &stmt_list);
1306 /* If we created initialization statements, insert them. */
1309 annotate_all_with_locus (&stmt_list,
1310 DECL_SOURCE_LOCATION (context));
1311 append_to_statement_list (BIND_EXPR_BODY (DECL_SAVED_TREE (context)),
1313 BIND_EXPR_BODY (DECL_SAVED_TREE (context)) = stmt_list;
1316 /* If a chain_decl was created, then it needs to be registered with
1317 struct function so that it gets initialized from the static chain
1318 register at the beginning of the function. */
1319 sf = DECL_STRUCT_FUNCTION (root->context);
1320 sf->static_chain_decl = root->chain_decl;
1322 /* Similarly for the non-local goto save area. */
1323 if (root->nl_goto_field)
1325 sf->nonlocal_goto_save_area
1326 = get_frame_field (root, context, root->nl_goto_field, NULL);
1327 sf->has_nonlocal_label = 1;
1330 /* Make sure all new local variables get inserted into the
1331 proper BIND_EXPR. */
1332 if (root->new_local_var_chain)
1333 declare_tmp_vars (root->new_local_var_chain,
1334 DECL_SAVED_TREE (root->context));
1336 /* Dump the translated tree function. */
1337 dump_function (TDI_nested, root->context);
1341 finalize_nesting_tree (struct nesting_info *root)
1346 finalize_nesting_tree (root->inner);
1347 finalize_nesting_tree_1 (root);
1353 /* Free the data structures allocated during this pass. */
1356 free_nesting_tree (struct nesting_info *root)
1358 struct nesting_info *next;
1362 free_nesting_tree (root->inner);
1363 htab_delete (root->var_map);
1371 /* Main entry point for this pass. Process FNDECL and all of its nested
1372 subroutines and turn them into something less tightly bound. */
1375 lower_nested_functions (tree fndecl)
1377 struct nesting_info *root;
1378 struct cgraph_node *cgn;
1380 /* If there are no nested functions, there's nothing to do. */
1381 cgn = cgraph_node (fndecl);
1385 root = create_nesting_tree (cgn);
1386 walk_all_functions (convert_nonlocal_reference, root);
1387 walk_all_functions (convert_local_reference, root);
1388 walk_all_functions (convert_nl_goto_reference, root);
1389 walk_all_functions (convert_nl_goto_receiver, root);
1390 convert_all_function_calls (root);
1391 finalize_nesting_tree (root);
1392 free_nesting_tree (root);
1395 #include "gt-tree-nested.h"