* arm.h (REVERSE_CONDITION): Define.
[official-gcc.git] / gcc / tree-nested.c
blob183d3aeb3458e803608025f7a95421d90f0363c8
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)
9 any later version.
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. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "rtl.h"
27 #include "tm_p.h"
28 #include "function.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"
34 #include "cgraph.h"
35 #include "expr.h"
36 #include "langhooks.h"
37 #include "ggc.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
66 inlinable.
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. */
80 struct var_map_elt
82 tree old;
83 tree new;
86 struct nesting_info
88 struct nesting_info *outer;
89 struct nesting_info *inner;
90 struct nesting_info *next;
92 htab_t var_map;
93 tree context;
94 tree new_local_var_chain;
95 tree frame_type;
96 tree frame_decl;
97 tree chain_field;
98 tree chain_decl;
99 tree nl_goto_field;
101 bool any_parm_remapped;
102 bool any_tramp_created;
106 /* Hashing and equality functions for nesting_info->var_map. */
108 static hashval_t
109 var_map_hash (const void *x)
111 const struct var_map_elt *a = x;
112 return htab_hash_pointer (a->old);
115 static int
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. */
130 static tree
131 create_tmp_var_for (struct nesting_info *info, tree type, const char *prefix)
133 tree tmp_var;
135 #if defined ENABLE_CHECKING
136 /* If the type is of variable size 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_ADDRESSABLE (type)
140 || (TYPE_SIZE_UNIT (type)
141 && TREE_CODE (TYPE_SIZE_UNIT (type)) != INTEGER_CST))
142 abort ();
143 #endif
145 tmp_var = create_tmp_var_raw (type, prefix);
146 DECL_CONTEXT (tmp_var) = info->context;
147 TREE_CHAIN (tmp_var) = info->new_local_var_chain;
148 DECL_SEEN_IN_BIND_EXPR_P (tmp_var) = 1;
149 info->new_local_var_chain = tmp_var;
151 return tmp_var;
154 /* Take the address of EXP. Mark it for addressability as necessary. */
156 static tree
157 build_addr (tree exp)
159 tree base = exp;
161 while (TREE_CODE (base) == REALPART_EXPR || TREE_CODE (base) == IMAGPART_EXPR
162 || handled_component_p (base))
163 base = TREE_OPERAND (base, 0);
165 if (DECL_P (base))
166 TREE_ADDRESSABLE (base) = 1;
168 return build1 (ADDR_EXPR, build_pointer_type (TREE_TYPE (exp)), exp);
171 /* Insert FIELD into TYPE, sorted by alignment requirements. */
173 static void
174 insert_field_into_struct (tree type, tree field)
176 tree *p;
178 DECL_CONTEXT (field) = type;
180 for (p = &TYPE_FIELDS (type); *p ; p = &TREE_CHAIN (*p))
181 if (DECL_ALIGN (field) >= DECL_ALIGN (*p))
182 break;
184 TREE_CHAIN (field) = *p;
185 *p = field;
188 /* Build or return the RECORD_TYPE that describes the frame state that is
189 shared between INFO->CONTEXT and its nested functions. This record will
190 not be complete until finalize_nesting_tree; up until that point we'll
191 be adding fields as necessary.
193 We also build the DECL that represents this frame in the function. */
195 static tree
196 get_frame_type (struct nesting_info *info)
198 tree type = info->frame_type;
199 if (!type)
201 char *name;
203 type = make_node (RECORD_TYPE);
205 name = concat ("FRAME.",
206 IDENTIFIER_POINTER (DECL_NAME (info->context)),
207 NULL);
208 TYPE_NAME (type) = get_identifier (name);
209 free (name);
211 info->frame_type = type;
212 info->frame_decl = create_tmp_var_for (info, type, "FRAME");
214 return type;
217 /* Return true if DECL should be referenced by pointer in the non-local
218 frame structure. */
220 static bool
221 use_pointer_in_frame (tree decl)
223 if (TREE_CODE (decl) == PARM_DECL)
225 /* It's illegal to copy TREE_ADDRESSABLE, impossible to copy variable
226 sized decls, and inefficient to copy large aggregates. Don't bother
227 moving anything but scalar variables. */
228 return AGGREGATE_TYPE_P (TREE_TYPE (decl));
230 else
232 /* Variable sized types make things "interesting" in the frame. */
233 return DECL_SIZE (decl) == NULL || !TREE_CONSTANT (DECL_SIZE (decl));
237 /* Given DECL, a non-locally accessed variable, find or create a field
238 in the non-local frame structure for the given nesting context. */
240 static tree
241 lookup_field_for_decl (struct nesting_info *info, tree decl,
242 enum insert_option insert)
244 struct var_map_elt *elt, dummy;
245 void **slot;
246 tree field;
248 dummy.old = decl;
249 slot = htab_find_slot (info->var_map, &dummy, insert);
250 if (!slot)
252 if (insert == INSERT)
253 abort ();
254 return NULL;
256 elt = *slot;
258 if (!elt && insert == INSERT)
260 field = make_node (FIELD_DECL);
261 DECL_NAME (field) = DECL_NAME (decl);
263 if (use_pointer_in_frame (decl))
265 TREE_TYPE (field) = build_pointer_type (TREE_TYPE (decl));
266 DECL_ALIGN (field) = TYPE_ALIGN (TREE_TYPE (field));
267 DECL_NONADDRESSABLE_P (field) = 1;
269 else
271 TREE_TYPE (field) = TREE_TYPE (decl);
272 DECL_SOURCE_LOCATION (field) = DECL_SOURCE_LOCATION (decl);
273 DECL_ALIGN (field) = DECL_ALIGN (decl);
274 DECL_USER_ALIGN (field) = DECL_USER_ALIGN (decl);
275 TREE_ADDRESSABLE (field) = TREE_ADDRESSABLE (decl);
276 DECL_NONADDRESSABLE_P (field) = !TREE_ADDRESSABLE (decl);
277 TREE_THIS_VOLATILE (field) = TREE_THIS_VOLATILE (decl);
280 insert_field_into_struct (get_frame_type (info), field);
282 elt = xmalloc (sizeof (*elt));
283 elt->old = decl;
284 elt->new = field;
285 *slot = elt;
287 if (TREE_CODE (decl) == PARM_DECL)
288 info->any_parm_remapped = true;
290 else
291 field = elt ? elt->new : NULL;
293 return field;
296 /* Build or return the variable that holds the static chain within
297 INFO->CONTEXT. This variable may only be used within INFO->CONTEXT. */
299 static tree
300 get_chain_decl (struct nesting_info *info)
302 tree decl = info->chain_decl;
303 if (!decl)
305 tree type;
307 type = get_frame_type (info->outer);
308 type = build_pointer_type (type);
310 /* Note that this variable is *not* entered into any BIND_EXPR;
311 the construction of this variable is handled specially in
312 expand_function_start and initialize_inlined_parameters.
313 Note also that it's represented as a parameter. This is more
314 close to the truth, since the initial value does come from
315 the caller. */
316 decl = build_decl (PARM_DECL, create_tmp_var_name ("CHAIN"), type);
317 DECL_ARTIFICIAL (decl) = 1;
318 DECL_IGNORED_P (decl) = 1;
319 TREE_USED (decl) = 1;
320 DECL_CONTEXT (decl) = info->context;
321 DECL_ARG_TYPE (decl) = type;
323 /* Tell tree-inline.c that we never write to this variable, so
324 it can copy-prop the replacement value immediately. */
325 TREE_READONLY (decl) = 1;
327 info->chain_decl = decl;
329 return decl;
332 /* Build or return the field within the non-local frame state that holds
333 the static chain for INFO->CONTEXT. This is the way to walk back up
334 multiple nesting levels. */
336 static tree
337 get_chain_field (struct nesting_info *info)
339 tree field = info->chain_field;
340 if (!field)
342 tree type = build_pointer_type (get_frame_type (info->outer));
344 field = make_node (FIELD_DECL);
345 DECL_NAME (field) = get_identifier ("__chain");
346 TREE_TYPE (field) = type;
347 DECL_ALIGN (field) = TYPE_ALIGN (type);
348 DECL_NONADDRESSABLE_P (field) = 1;
350 insert_field_into_struct (get_frame_type (info), field);
352 info->chain_field = field;
354 return field;
357 /* Copy EXP into a temporary. Allocate the temporary in the context of
358 INFO and insert the initialization statement before TSI. */
360 static tree
361 init_tmp_var (struct nesting_info *info, tree exp, tree_stmt_iterator *tsi)
363 tree t, stmt;
365 t = create_tmp_var_for (info, TREE_TYPE (exp), NULL);
366 stmt = build (MODIFY_EXPR, TREE_TYPE (t), t, exp);
367 SET_EXPR_LOCUS (stmt, EXPR_LOCUS (tsi_stmt (*tsi)));
368 tsi_link_before (tsi, stmt, TSI_SAME_STMT);
370 return t;
373 /* Similarly, but only do so to force EXP to satisfy is_gimple_val. */
375 static tree
376 tsi_gimplify_val (struct nesting_info *info, tree exp, tree_stmt_iterator *tsi)
378 if (is_gimple_val (exp))
379 return exp;
380 else
381 return init_tmp_var (info, exp, tsi);
384 /* Build or return the type used to represent a nested function trampoline. */
386 static GTY(()) tree trampoline_type;
388 static tree
389 get_trampoline_type (void)
391 tree record, t;
392 unsigned align, size;
394 if (trampoline_type)
395 return trampoline_type;
397 align = TRAMPOLINE_ALIGNMENT;
398 size = TRAMPOLINE_SIZE;
400 /* If we won't be able to guarantee alignment simply via TYPE_ALIGN,
401 then allocate extra space so that we can do dynamic alignment. */
402 if (align > STACK_BOUNDARY)
404 size += ((align/BITS_PER_UNIT) - 1) & -(STACK_BOUNDARY/BITS_PER_UNIT);
405 align = STACK_BOUNDARY;
408 t = build_index_type (build_int_cst (NULL_TREE, size - 1));
409 t = build_array_type (char_type_node, t);
410 t = build_decl (FIELD_DECL, get_identifier ("__data"), t);
411 DECL_ALIGN (t) = align;
412 DECL_USER_ALIGN (t) = 1;
414 record = make_node (RECORD_TYPE);
415 TYPE_NAME (record) = get_identifier ("__builtin_trampoline");
416 TYPE_FIELDS (record) = t;
417 layout_type (record);
419 return record;
422 /* Given DECL, a nested function, find or create a field in the non-local
423 frame structure for a trampoline for this function. */
425 static tree
426 lookup_tramp_for_decl (struct nesting_info *info, tree decl,
427 enum insert_option insert)
429 struct var_map_elt *elt, dummy;
430 void **slot;
431 tree field;
433 dummy.old = decl;
434 slot = htab_find_slot (info->var_map, &dummy, insert);
435 if (!slot)
437 if (insert == INSERT)
438 abort ();
439 return NULL;
441 elt = *slot;
443 if (!elt && insert == INSERT)
445 field = make_node (FIELD_DECL);
446 DECL_NAME (field) = DECL_NAME (decl);
447 TREE_TYPE (field) = get_trampoline_type ();
448 TREE_ADDRESSABLE (field) = 1;
450 insert_field_into_struct (get_frame_type (info), field);
452 elt = xmalloc (sizeof (*elt));
453 elt->old = decl;
454 elt->new = field;
455 *slot = elt;
457 info->any_tramp_created = true;
459 else
460 field = elt ? elt->new : NULL;
462 return field;
465 /* Build or return the field within the non-local frame state that holds
466 the non-local goto "jmp_buf". The buffer itself is maintained by the
467 rtl middle-end as dynamic stack space is allocated. */
469 static tree
470 get_nl_goto_field (struct nesting_info *info)
472 tree field = info->nl_goto_field;
473 if (!field)
475 unsigned size;
476 tree type;
478 /* For __builtin_nonlocal_goto, we need N words. The first is the
479 frame pointer, the rest is for the target's stack pointer save
480 area. The number of words is controlled by STACK_SAVEAREA_MODE;
481 not the best interface, but it'll do for now. */
482 if (Pmode == ptr_mode)
483 type = ptr_type_node;
484 else
485 type = lang_hooks.types.type_for_mode (Pmode, 1);
487 size = GET_MODE_SIZE (STACK_SAVEAREA_MODE (SAVE_NONLOCAL));
488 size = size / GET_MODE_SIZE (Pmode);
489 size = size + 1;
491 type = build_array_type
492 (type, build_index_type (build_int_cst (NULL_TREE, size)));
494 field = make_node (FIELD_DECL);
495 DECL_NAME (field) = get_identifier ("__nl_goto_buf");
496 TREE_TYPE (field) = type;
497 DECL_ALIGN (field) = TYPE_ALIGN (type);
498 TREE_ADDRESSABLE (field) = 1;
500 insert_field_into_struct (get_frame_type (info), field);
502 info->nl_goto_field = field;
505 return field;
508 /* Convenience routines to walk all statements of a gimple function.
510 For each statement, we invoke CALLBACK via walk_tree. The passed
511 data is a walk_stmt_info structure. Of note here is a TSI that
512 points to the current statement being walked. The VAL_ONLY flag
513 that indicates whether the *TP being examined may be replaced
514 with something that matches is_gimple_val (if true) or something
515 slightly more complicated (if false). "Something" technically
516 means the common subset of is_gimple_lvalue and is_gimple_rhs,
517 but we never try to form anything more complicated than that, so
518 we don't bother checking. */
520 struct walk_stmt_info
522 walk_tree_fn callback;
523 tree_stmt_iterator tsi;
524 struct nesting_info *info;
525 bool val_only;
528 /* A subroutine of walk_function. Iterate over all sub-statements of *TP. */
530 static void
531 walk_stmts (struct walk_stmt_info *wi, tree *tp)
533 tree t = *tp;
534 if (!t)
535 return;
537 switch (TREE_CODE (t))
539 case STATEMENT_LIST:
541 tree_stmt_iterator i;
542 for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
544 wi->tsi = i;
545 walk_stmts (wi, tsi_stmt_ptr (i));
548 break;
550 case COND_EXPR:
551 walk_tree (&COND_EXPR_COND (t), wi->callback, wi, NULL);
552 walk_stmts (wi, &COND_EXPR_THEN (t));
553 walk_stmts (wi, &COND_EXPR_ELSE (t));
554 break;
555 case CATCH_EXPR:
556 walk_stmts (wi, &CATCH_BODY (t));
557 break;
558 case EH_FILTER_EXPR:
559 walk_stmts (wi, &EH_FILTER_FAILURE (t));
560 break;
561 case TRY_CATCH_EXPR:
562 case TRY_FINALLY_EXPR:
563 walk_stmts (wi, &TREE_OPERAND (t, 0));
564 walk_stmts (wi, &TREE_OPERAND (t, 1));
565 break;
566 case BIND_EXPR:
567 walk_stmts (wi, &BIND_EXPR_BODY (t));
568 break;
570 case RETURN_EXPR:
571 walk_stmts (wi, &TREE_OPERAND (t, 0));
572 break;
574 case MODIFY_EXPR:
575 /* The immediate arguments of a MODIFY_EXPR may use COMPONENT_REF. */
576 wi->val_only = false;
577 walk_tree (&TREE_OPERAND (t, 0), wi->callback, wi, NULL);
578 wi->val_only = false;
579 walk_tree (&TREE_OPERAND (t, 1), wi->callback, wi, NULL);
580 wi->val_only = true;
581 break;
583 default:
584 wi->val_only = true;
585 walk_tree (tp, wi->callback, wi, NULL);
586 break;
590 /* Invoke CALLBACK on all statements of INFO->CONTEXT. */
592 static void
593 walk_function (walk_tree_fn callback, struct nesting_info *info)
595 struct walk_stmt_info wi;
597 memset (&wi, 0, sizeof (wi));
598 wi.callback = callback;
599 wi.info = info;
600 wi.val_only = true;
602 walk_stmts (&wi, &DECL_SAVED_TREE (info->context));
605 /* Similarly for ROOT and all functions nested underneath, depth first. */
607 static void
608 walk_all_functions (walk_tree_fn callback, struct nesting_info *root)
612 if (root->inner)
613 walk_all_functions (callback, root->inner);
614 walk_function (callback, root);
615 root = root->next;
617 while (root);
621 /* Construct our local datastructure describing the function nesting
622 tree rooted by CGN. */
624 static struct nesting_info *
625 create_nesting_tree (struct cgraph_node *cgn)
627 struct nesting_info *info = xcalloc (1, sizeof (*info));
628 info->var_map = htab_create (7, var_map_hash, var_map_eq, free);
629 info->context = cgn->decl;
631 for (cgn = cgn->nested; cgn ; cgn = cgn->next_nested)
633 struct nesting_info *sub = create_nesting_tree (cgn);
634 sub->outer = info;
635 sub->next = info->inner;
636 info->inner = sub;
639 return info;
642 /* Return an expression computing the static chain for TARGET_CONTEXT
643 from INFO->CONTEXT. Insert any necessary computations before TSI. */
645 static tree
646 get_static_chain (struct nesting_info *info, tree target_context,
647 tree_stmt_iterator *tsi)
649 struct nesting_info *i;
650 tree x;
652 if (info->context == target_context)
654 x = build_addr (info->frame_decl);
656 else
658 x = get_chain_decl (info);
660 for (i = info->outer; i->context != target_context; i = i->outer)
662 tree field = get_chain_field (i);
664 x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
665 x = build (COMPONENT_REF, TREE_TYPE (field), x, field, NULL_TREE);
666 x = init_tmp_var (info, x, tsi);
670 return x;
673 /* Return an expression referencing FIELD from TARGET_CONTEXT's non-local
674 frame as seen from INFO->CONTEXT. Insert any necessary computations
675 before TSI. */
677 static tree
678 get_frame_field (struct nesting_info *info, tree target_context,
679 tree field, tree_stmt_iterator *tsi)
681 struct nesting_info *i;
682 tree x;
684 if (info->context == target_context)
686 /* Make sure frame_decl gets created. */
687 (void) get_frame_type (info);
688 x = info->frame_decl;
690 else
692 x = get_chain_decl (info);
694 for (i = info->outer; i->context != target_context; i = i->outer)
696 tree field = get_chain_field (i);
698 x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
699 x = build (COMPONENT_REF, TREE_TYPE (field), x, field, NULL_TREE);
700 x = init_tmp_var (info, x, tsi);
703 x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
706 x = build (COMPONENT_REF, TREE_TYPE (field), x, field, NULL_TREE);
707 return x;
710 /* Called via walk_function+walk_tree, rewrite all references to VAR
711 and PARM_DECLs that belong to outer functions.
713 The rewrite will involve some number of structure accesses back up
714 the static chain. E.g. for a variable FOO up one nesting level it'll
715 be CHAIN->FOO. For two levels it'll be CHAIN->__chain->FOO. Further
716 indirections apply to decls for which use_pointer_in_frame is true. */
718 static tree
719 convert_nonlocal_reference (tree *tp, int *walk_subtrees, void *data)
721 struct walk_stmt_info *wi = data;
722 struct nesting_info *info = wi->info;
723 tree t = *tp;
725 *walk_subtrees = 0;
726 switch (TREE_CODE (t))
728 case VAR_DECL:
729 /* Non-automatic variables are never processed. */
730 if (TREE_STATIC (t) || DECL_EXTERNAL (t))
731 break;
732 /* FALLTHRU */
734 case PARM_DECL:
735 if (decl_function_context (t) != info->context)
737 tree target_context = decl_function_context (t);
738 struct nesting_info *i;
739 tree x;
741 for (i = info->outer; i->context != target_context; i = i->outer)
742 continue;
743 x = lookup_field_for_decl (i, t, INSERT);
744 x = get_frame_field (info, target_context, x, &wi->tsi);
745 if (use_pointer_in_frame (t))
747 x = init_tmp_var (info, x, &wi->tsi);
748 x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
750 if (wi->val_only)
751 x = init_tmp_var (info, x, &wi->tsi);
753 *tp = x;
755 break;
757 case GOTO_EXPR:
758 /* Don't walk non-local gotos for now. */
759 if (TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL)
761 *walk_subtrees = 1;
762 wi->val_only = true;
764 break;
766 case LABEL_DECL:
767 /* We're taking the address of a label from a parent function, but
768 this is not itself a non-local goto. Mark the label such that it
769 will not be deleted, much as we would with a label address in
770 static storage. */
771 if (decl_function_context (t) != info->context)
772 FORCED_LABEL (t) = 1;
773 break;
775 case ADDR_EXPR:
777 bool save_val_only = wi->val_only;
778 tree save_sub = TREE_OPERAND (t, 0);
780 wi->val_only = false;
781 walk_tree (&TREE_OPERAND (t, 0), convert_nonlocal_reference, wi, NULL);
782 wi->val_only = true;
784 if (save_sub != TREE_OPERAND (t, 0))
786 /* If we changed anything, then TREE_INVARIANT is be wrong,
787 since we're no longer directly referencing a decl. */
788 TREE_INVARIANT (t) = 0;
790 /* If the callback converted the address argument in a context
791 where we only accept variables (and min_invariant, presumably),
792 then compute the address into a temporary. */
793 if (save_val_only)
794 *tp = tsi_gimplify_val (wi->info, t, &wi->tsi);
797 break;
799 case REALPART_EXPR:
800 case IMAGPART_EXPR:
801 case COMPONENT_REF:
802 case ARRAY_REF:
803 case ARRAY_RANGE_REF:
804 case BIT_FIELD_REF:
805 /* Go down this entire nest and just look at the final prefix and
806 anything that describes the references. Otherwise, we lose track
807 of whether a NOP_EXPR or VIEW_CONVERT_EXPR needs a simple value. */
808 wi->val_only = true;
809 for (; handled_component_p (t)
810 || TREE_CODE (t) == REALPART_EXPR || TREE_CODE (t) == IMAGPART_EXPR;
811 tp = &TREE_OPERAND (t, 0), t = *tp)
813 if (TREE_CODE (t) == COMPONENT_REF)
814 walk_tree (&TREE_OPERAND (t, 2), convert_nonlocal_reference, wi,
815 NULL);
816 else if (TREE_CODE (t) == ARRAY_REF
817 || TREE_CODE (t) == ARRAY_RANGE_REF)
819 walk_tree (&TREE_OPERAND (t, 1), convert_nonlocal_reference, wi,
820 NULL);
821 walk_tree (&TREE_OPERAND (t, 2), convert_nonlocal_reference, wi,
822 NULL);
823 walk_tree (&TREE_OPERAND (t, 3), convert_nonlocal_reference, wi,
824 NULL);
826 else if (TREE_CODE (t) == BIT_FIELD_REF)
828 walk_tree (&TREE_OPERAND (t, 1), convert_nonlocal_reference, wi,
829 NULL);
830 walk_tree (&TREE_OPERAND (t, 2), convert_nonlocal_reference, wi,
831 NULL);
834 wi->val_only = false;
835 walk_tree (tp, convert_nonlocal_reference, wi, NULL);
836 break;
838 default:
839 if (!DECL_P (t) && !TYPE_P (t))
841 *walk_subtrees = 1;
842 wi->val_only = true;
844 break;
847 return NULL_TREE;
850 /* Called via walk_function+walk_tree, rewrite all references to VAR
851 and PARM_DECLs that were referenced by inner nested functions.
852 The rewrite will be a structure reference to the local frame variable. */
854 static tree
855 convert_local_reference (tree *tp, int *walk_subtrees, void *data)
857 struct walk_stmt_info *wi = data;
858 struct nesting_info *info = wi->info;
859 tree t = *tp, field, x;
861 switch (TREE_CODE (t))
863 case VAR_DECL:
864 /* Non-automatic variables are never processed. */
865 if (TREE_STATIC (t) || DECL_EXTERNAL (t))
866 break;
867 /* FALLTHRU */
869 case PARM_DECL:
870 if (decl_function_context (t) == info->context)
872 /* If we copied a pointer to the frame, then the original decl
873 is used unchanged in the parent function. */
874 if (use_pointer_in_frame (t))
875 break;
877 /* No need to transform anything if no child references the
878 variable. */
879 field = lookup_field_for_decl (info, t, NO_INSERT);
880 if (!field)
881 break;
883 x = get_frame_field (info, info->context, field, &wi->tsi);
884 if (wi->val_only)
885 x = init_tmp_var (info, x, &wi->tsi);
886 *tp = x;
888 break;
890 case ADDR_EXPR:
892 bool save_val_only = wi->val_only;
893 tree save_sub = TREE_OPERAND (t, 0);
895 wi->val_only = false;
896 walk_tree (&TREE_OPERAND (t, 0), convert_local_reference, wi, NULL);
897 wi->val_only = save_val_only;
899 /* If we converted anything ... */
900 if (TREE_OPERAND (t, 0) != save_sub)
902 /* Then the frame decl is now addressable. */
903 TREE_ADDRESSABLE (info->frame_decl) = 1;
905 /* If we are in a context where we only accept values, then
906 compute the address into a temporary. */
907 if (save_val_only)
908 *tp = tsi_gimplify_val (wi->info, t, &wi->tsi);
911 break;
913 case REALPART_EXPR:
914 case IMAGPART_EXPR:
915 case COMPONENT_REF:
916 case ARRAY_REF:
917 case ARRAY_RANGE_REF:
918 case BIT_FIELD_REF:
919 /* Go down this entire nest and just look at the final prefix and
920 anything that describes the references. Otherwise, we lose track
921 of whether a NOP_EXPR or VIEW_CONVERT_EXPR needs a simple value. */
922 wi->val_only = true;
923 for (; handled_component_p (t)
924 || TREE_CODE (t) == REALPART_EXPR || TREE_CODE (t) == IMAGPART_EXPR;
925 tp = &TREE_OPERAND (t, 0), t = *tp)
927 if (TREE_CODE (t) == COMPONENT_REF)
928 walk_tree (&TREE_OPERAND (t, 2), convert_local_reference, wi,
929 NULL);
930 else if (TREE_CODE (t) == ARRAY_REF
931 || TREE_CODE (t) == ARRAY_RANGE_REF)
933 walk_tree (&TREE_OPERAND (t, 1), convert_local_reference, wi,
934 NULL);
935 walk_tree (&TREE_OPERAND (t, 2), convert_local_reference, wi,
936 NULL);
937 walk_tree (&TREE_OPERAND (t, 3), convert_local_reference, wi,
938 NULL);
940 else if (TREE_CODE (t) == BIT_FIELD_REF)
942 walk_tree (&TREE_OPERAND (t, 1), convert_local_reference, wi,
943 NULL);
944 walk_tree (&TREE_OPERAND (t, 2), convert_local_reference, wi,
945 NULL);
948 wi->val_only = false;
949 walk_tree (tp, convert_local_reference, wi, NULL);
950 break;
952 default:
953 if (!DECL_P (t) && !TYPE_P (t))
955 *walk_subtrees = 1;
956 wi->val_only = true;
958 break;
961 return NULL_TREE;
964 /* Called via walk_function+walk_tree, rewrite all GOTO_EXPRs that
965 reference labels from outer functions. The rewrite will be a
966 call to __builtin_nonlocal_goto. */
968 static tree
969 convert_nl_goto_reference (tree *tp, int *walk_subtrees, void *data)
971 struct walk_stmt_info *wi = data;
972 struct nesting_info *info = wi->info, *i;
973 tree t = *tp, label, new_label, target_context, x, arg, field;
974 struct var_map_elt *elt;
975 void **slot;
977 *walk_subtrees = 0;
978 if (TREE_CODE (t) != GOTO_EXPR)
979 return NULL_TREE;
980 label = GOTO_DESTINATION (t);
981 if (TREE_CODE (label) != LABEL_DECL)
982 return NULL_TREE;
983 target_context = decl_function_context (label);
984 if (target_context == info->context)
985 return NULL_TREE;
987 for (i = info->outer; target_context != i->context; i = i->outer)
988 continue;
990 /* The original user label may also be use for a normal goto, therefore
991 we must create a new label that will actually receive the abnormal
992 control transfer. This new label will be marked LABEL_NONLOCAL; this
993 mark will trigger proper behavior in the cfg, as well as cause the
994 (hairy target-specific) non-local goto receiver code to be generated
995 when we expand rtl. */
996 new_label = create_artificial_label ();
997 DECL_NONLOCAL (new_label) = 1;
999 /* Enter this association into var_map so that we can insert the new
1000 label into the IL during a second pass. */
1001 elt = xmalloc (sizeof (*elt));
1002 elt->old = label;
1003 elt->new = new_label;
1004 slot = htab_find_slot (i->var_map, elt, INSERT);
1005 *slot = elt;
1007 /* Build: __builtin_nl_goto(new_label, &chain->nl_goto_field). */
1008 field = get_nl_goto_field (i);
1009 x = get_frame_field (info, target_context, field, &wi->tsi);
1010 x = build_addr (x);
1011 x = tsi_gimplify_val (info, x, &wi->tsi);
1012 arg = tree_cons (NULL, x, NULL);
1013 x = build_addr (new_label);
1014 arg = tree_cons (NULL, x, arg);
1015 x = implicit_built_in_decls[BUILT_IN_NONLOCAL_GOTO];
1016 x = build_function_call_expr (x, arg);
1018 SET_EXPR_LOCUS (x, EXPR_LOCUS (tsi_stmt (wi->tsi)));
1019 *tsi_stmt_ptr (wi->tsi) = x;
1021 return NULL_TREE;
1024 /* Called via walk_function+walk_tree, rewrite all LABEL_EXPRs that
1025 are referenced via nonlocal goto from a nested function. The rewrite
1026 will involve installing a newly generated DECL_NONLOCAL label, and
1027 (potentially) a branch around the rtl gunk that is assumed to be
1028 attached to such a label. */
1030 static tree
1031 convert_nl_goto_receiver (tree *tp, int *walk_subtrees, void *data)
1033 struct walk_stmt_info *wi = data;
1034 struct nesting_info *info = wi->info;
1035 tree t = *tp, label, new_label, x;
1036 struct var_map_elt *elt, dummy;
1037 tree_stmt_iterator tmp_tsi;
1039 *walk_subtrees = 0;
1040 if (TREE_CODE (t) != LABEL_EXPR)
1041 return NULL_TREE;
1042 label = LABEL_EXPR_LABEL (t);
1044 dummy.old = label;
1045 elt = htab_find (info->var_map, &dummy);
1046 if (!elt)
1047 return NULL_TREE;
1048 new_label = elt->new;
1050 /* If there's any possibility that the previous statement falls through,
1051 then we must branch around the new non-local label. */
1052 tmp_tsi = wi->tsi;
1053 tsi_prev (&tmp_tsi);
1054 if (tsi_end_p (tmp_tsi) || block_may_fallthru (tsi_stmt (tmp_tsi)))
1056 x = build1 (GOTO_EXPR, void_type_node, label);
1057 tsi_link_before (&wi->tsi, x, TSI_SAME_STMT);
1059 x = build1 (LABEL_EXPR, void_type_node, new_label);
1060 tsi_link_before (&wi->tsi, x, TSI_SAME_STMT);
1062 return NULL_TREE;
1065 /* Called via walk_function+walk_tree, rewrite all references to addresses
1066 of nested functions that require the use of trampolines. The rewrite
1067 will involve a reference a trampoline generated for the occasion. */
1069 static tree
1070 convert_tramp_reference (tree *tp, int *walk_subtrees, void *data)
1072 struct walk_stmt_info *wi = data;
1073 struct nesting_info *info = wi->info, *i;
1074 tree t = *tp, decl, target_context, x, arg;
1076 *walk_subtrees = 0;
1077 switch (TREE_CODE (t))
1079 case ADDR_EXPR:
1080 /* Build
1081 T.1 = &CHAIN->tramp;
1082 T.2 = __builtin_adjust_trampoline (T.1);
1083 T.3 = (func_type)T.2;
1086 decl = TREE_OPERAND (t, 0);
1087 if (TREE_CODE (decl) != FUNCTION_DECL)
1088 break;
1090 /* Only need to process nested functions. */
1091 target_context = decl_function_context (decl);
1092 if (!target_context)
1093 break;
1095 /* If the nested function doesn't use a static chain, then
1096 it doesn't need a trampoline. */
1097 if (DECL_NO_STATIC_CHAIN (decl))
1098 break;
1100 /* Lookup the immediate parent of the callee, as that's where
1101 we need to insert the trampoline. */
1102 for (i = info; i->context != target_context; i = i->outer)
1103 continue;
1104 x = lookup_tramp_for_decl (i, decl, INSERT);
1106 /* Compute the address of the field holding the trampoline. */
1107 x = get_frame_field (info, target_context, x, &wi->tsi);
1108 x = build_addr (x);
1109 x = tsi_gimplify_val (info, x, &wi->tsi);
1110 arg = tree_cons (NULL, x, NULL);
1112 /* Do machine-specific ugliness. Normally this will involve
1113 computing extra alignment, but it can really be anything. */
1114 x = implicit_built_in_decls[BUILT_IN_ADJUST_TRAMPOLINE];
1115 x = build_function_call_expr (x, arg);
1116 x = init_tmp_var (info, x, &wi->tsi);
1118 /* Cast back to the proper function type. */
1119 x = build1 (NOP_EXPR, TREE_TYPE (t), x);
1120 x = init_tmp_var (info, x, &wi->tsi);
1122 *tp = x;
1123 break;
1125 case CALL_EXPR:
1126 /* Only walk call arguments, lest we generate trampolines for
1127 direct calls. */
1128 walk_tree (&TREE_OPERAND (t, 1), convert_tramp_reference, wi, NULL);
1129 break;
1131 default:
1132 if (!DECL_P (t) && !TYPE_P (t))
1133 *walk_subtrees = 1;
1134 break;
1137 return NULL_TREE;
1140 /* Called via walk_function+walk_tree, rewrite all CALL_EXPRs that
1141 reference nested functions to make sure that the static chain is
1142 set up properly for the call. */
1144 static tree
1145 convert_call_expr (tree *tp, int *walk_subtrees, void *data)
1147 struct walk_stmt_info *wi = data;
1148 struct nesting_info *info = wi->info;
1149 tree t = *tp, decl, target_context;
1151 *walk_subtrees = 0;
1152 switch (TREE_CODE (t))
1154 case CALL_EXPR:
1155 decl = get_callee_fndecl (t);
1156 if (!decl)
1157 break;
1158 target_context = decl_function_context (decl);
1159 if (target_context && !DECL_NO_STATIC_CHAIN (decl))
1160 TREE_OPERAND (t, 2)
1161 = get_static_chain (info, target_context, &wi->tsi);
1162 break;
1164 case RETURN_EXPR:
1165 case MODIFY_EXPR:
1166 case WITH_SIZE_EXPR:
1167 /* Only return modify and with_size_expr may contain calls. */
1168 *walk_subtrees = 1;
1169 break;
1171 default:
1172 break;
1175 return NULL_TREE;
1178 /* Walk the nesting tree starting with ROOT, depth first. Convert all
1179 trampolines and call expressions. On the way back up, determine if
1180 a nested function actually uses its static chain; if not, remember that. */
1182 static void
1183 convert_all_function_calls (struct nesting_info *root)
1187 if (root->inner)
1188 convert_all_function_calls (root->inner);
1190 walk_function (convert_tramp_reference, root);
1191 walk_function (convert_call_expr, root);
1193 /* If the function does not use a static chain, then remember that. */
1194 if (root->outer && !root->chain_decl && !root->chain_field)
1195 DECL_NO_STATIC_CHAIN (root->context) = 1;
1196 else
1198 #ifdef ENABLE_CHECKING
1199 if (DECL_NO_STATIC_CHAIN (root->context))
1200 abort ();
1201 #endif
1204 root = root->next;
1206 while (root);
1209 /* Do "everything else" to clean up or complete state collected by the
1210 various walking passes -- lay out the types and decls, generate code
1211 to initialize the frame decl, store critical expressions in the
1212 struct function for rtl to find. */
1214 static void
1215 finalize_nesting_tree_1 (struct nesting_info *root)
1217 tree stmt_list = NULL;
1218 tree context = root->context;
1219 struct function *sf;
1221 /* If we created a non-local frame type or decl, we need to lay them
1222 out at this time. */
1223 if (root->frame_type)
1225 layout_type (root->frame_type);
1226 layout_decl (root->frame_decl, 0);
1229 /* If any parameters were referenced non-locally, then we need to
1230 insert a copy. Likewise, if any variables were referenced by
1231 pointer, we need to initialize the address. */
1232 if (root->any_parm_remapped)
1234 tree p;
1235 for (p = DECL_ARGUMENTS (context); p ; p = TREE_CHAIN (p))
1237 tree field, x, y;
1239 field = lookup_field_for_decl (root, p, NO_INSERT);
1240 if (!field)
1241 continue;
1243 if (use_pointer_in_frame (p))
1244 x = build_addr (p);
1245 else
1246 x = p;
1248 y = build (COMPONENT_REF, TREE_TYPE (field),
1249 root->frame_decl, field, NULL_TREE);
1250 x = build (MODIFY_EXPR, TREE_TYPE (field), y, x);
1251 append_to_statement_list (x, &stmt_list);
1255 /* If a chain_field was created, then it needs to be initialized
1256 from chain_decl. */
1257 if (root->chain_field)
1259 tree x = build (COMPONENT_REF, TREE_TYPE (root->chain_field),
1260 root->frame_decl, root->chain_field, NULL_TREE);
1261 x = build (MODIFY_EXPR, TREE_TYPE (x), x, get_chain_decl (root));
1262 append_to_statement_list (x, &stmt_list);
1265 /* If trampolines were created, then we need to initialize them. */
1266 if (root->any_tramp_created)
1268 struct nesting_info *i;
1269 for (i = root->inner; i ; i = i->next)
1271 tree arg, x, field;
1273 field = lookup_tramp_for_decl (root, i->context, NO_INSERT);
1274 if (!field)
1275 continue;
1277 if (DECL_NO_STATIC_CHAIN (i->context))
1278 x = null_pointer_node;
1279 else
1280 x = build_addr (root->frame_decl);
1281 arg = tree_cons (NULL, x, NULL);
1283 x = build_addr (i->context);
1284 arg = tree_cons (NULL, x, arg);
1286 x = build (COMPONENT_REF, TREE_TYPE (field),
1287 root->frame_decl, field, NULL_TREE);
1288 x = build_addr (x);
1289 arg = tree_cons (NULL, x, arg);
1291 x = implicit_built_in_decls[BUILT_IN_INIT_TRAMPOLINE];
1292 x = build_function_call_expr (x, arg);
1294 append_to_statement_list (x, &stmt_list);
1298 /* If we created initialization statements, insert them. */
1299 if (stmt_list)
1301 annotate_all_with_locus (&stmt_list,
1302 DECL_SOURCE_LOCATION (context));
1303 append_to_statement_list (BIND_EXPR_BODY (DECL_SAVED_TREE (context)),
1304 &stmt_list);
1305 BIND_EXPR_BODY (DECL_SAVED_TREE (context)) = stmt_list;
1308 /* If a chain_decl was created, then it needs to be registered with
1309 struct function so that it gets initialized from the static chain
1310 register at the beginning of the function. */
1311 sf = DECL_STRUCT_FUNCTION (root->context);
1312 sf->static_chain_decl = root->chain_decl;
1314 /* Similarly for the non-local goto save area. */
1315 if (root->nl_goto_field)
1317 sf->nonlocal_goto_save_area
1318 = get_frame_field (root, context, root->nl_goto_field, NULL);
1319 sf->has_nonlocal_label = 1;
1322 /* Make sure all new local variables get inserted into the
1323 proper BIND_EXPR. */
1324 if (root->new_local_var_chain)
1325 declare_tmp_vars (root->new_local_var_chain,
1326 DECL_SAVED_TREE (root->context));
1328 /* Dump the translated tree function. */
1329 dump_function (TDI_nested, root->context);
1332 static void
1333 finalize_nesting_tree (struct nesting_info *root)
1337 if (root->inner)
1338 finalize_nesting_tree (root->inner);
1339 finalize_nesting_tree_1 (root);
1340 root = root->next;
1342 while (root);
1345 /* Free the data structures allocated during this pass. */
1347 static void
1348 free_nesting_tree (struct nesting_info *root)
1350 struct nesting_info *next;
1353 if (root->inner)
1354 free_nesting_tree (root->inner);
1355 htab_delete (root->var_map);
1356 next = root->next;
1357 free (root);
1358 root = next;
1360 while (root);
1363 /* Main entry point for this pass. Process FNDECL and all of its nested
1364 subroutines and turn them into something less tightly bound. */
1366 void
1367 lower_nested_functions (tree fndecl)
1369 struct nesting_info *root;
1370 struct cgraph_node *cgn;
1372 /* If there are no nested functions, there's nothing to do. */
1373 cgn = cgraph_node (fndecl);
1374 if (!cgn->nested)
1375 return;
1377 root = create_nesting_tree (cgn);
1378 walk_all_functions (convert_nonlocal_reference, root);
1379 walk_all_functions (convert_local_reference, root);
1380 walk_all_functions (convert_nl_goto_reference, root);
1381 walk_all_functions (convert_nl_goto_receiver, root);
1382 convert_all_function_calls (root);
1383 finalize_nesting_tree (root);
1384 free_nesting_tree (root);
1387 #include "gt-tree-nested.h"