1 /* Control and data flow functions for trees.
2 Copyright 2001, 2002 Free Software Foundation, Inc.
3 Contributed by Alexandre Oliva <aoliva@redhat.com>
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
24 #include "coretypes.h"
28 #include "tree-inline.h"
34 #include "insn-config.h"
35 #include "integrate.h"
38 #include "splay-tree.h"
39 #include "langhooks.h"
41 /* This should be eventually be generalized to other languages, but
42 this would require a shared function-as-trees infrastructure. */
43 #ifndef INLINER_FOR_JAVA
45 #else /* INLINER_FOR_JAVA */
47 #include "java-tree.h"
48 #endif /* INLINER_FOR_JAVA */
50 /* 0 if we should not perform inlining.
51 1 if we should expand functions calls inline at the tree level.
52 2 if we should consider *all* functions to be inline
55 int flag_inline_trees = 0;
59 o In order to make inlining-on-trees work, we pessimized
60 function-local static constants. In particular, they are now
61 always output, even when not addressed. Fix this by treating
62 function-local static constants just like global static
63 constants; the back-end already knows not to output them if they
66 o Provide heuristics to clamp inlining of recursive template
69 /* Data required for function inlining. */
71 typedef struct inline_data
73 /* A stack of the functions we are inlining. For example, if we are
74 compiling `f', which calls `g', which calls `h', and we are
75 inlining the body of `h', the stack will contain, `h', followed
76 by `g', followed by `f'. The first few elements of the stack may
77 contain other functions that we know we should not recurse into,
78 even though they are not directly being inlined. */
80 /* The index of the first element of FNS that really represents an
82 unsigned first_inlined_fn;
83 /* The label to jump to when a return statement is encountered. If
84 this value is NULL, then return statements will simply be
85 remapped as return statements, rather than as jumps. */
87 /* The map from local declarations in the inlined function to
88 equivalents in the function into which it is being inlined. */
90 /* Nonzero if we are currently within the cleanup for a
92 int in_target_cleanup_p;
93 /* A list of the functions current function has inlined. */
94 varray_type inlined_fns;
95 /* The approximate number of statements we have inlined in the
96 current call stack. */
98 /* We use the same mechanism to build clones that we do to perform
99 inlining. However, there are a few places where we need to
100 distinguish between those two situations. This flag is true if
101 we are cloning, rather than inlining. */
103 /* Hash table used to prevent walk_tree from visiting the same node
104 umpteen million times. */
106 /* Decl of function we are inlining into. */
112 static tree declare_return_variable PARAMS ((inline_data *, tree, tree *));
113 static tree copy_body_r PARAMS ((tree *, int *, void *));
114 static tree copy_body PARAMS ((inline_data *));
115 static tree expand_call_inline PARAMS ((tree *, int *, void *));
116 static void expand_calls_inline PARAMS ((tree *, inline_data *));
117 static int inlinable_function_p PARAMS ((tree, inline_data *));
118 static tree remap_decl PARAMS ((tree, inline_data *));
119 #ifndef INLINER_FOR_JAVA
120 static tree initialize_inlined_parameters PARAMS ((inline_data *, tree, tree));
121 static void remap_block PARAMS ((tree, tree, inline_data *));
122 static void copy_scope_stmt PARAMS ((tree *, int *, inline_data *));
123 #else /* INLINER_FOR_JAVA */
124 static tree initialize_inlined_parameters PARAMS ((inline_data *, tree, tree, tree));
125 static void remap_block PARAMS ((tree *, tree, inline_data *));
126 static tree add_stmt_to_compound PARAMS ((tree, tree, tree));
127 #endif /* INLINER_FOR_JAVA */
128 static tree find_alloca_call_1 PARAMS ((tree *, int *, void *));
129 static tree find_alloca_call PARAMS ((tree));
130 static tree find_builtin_longjmp_call_1 PARAMS ((tree *, int *, void *));
131 static tree find_builtin_longjmp_call PARAMS ((tree));
133 /* The approximate number of instructions per statement. This number
134 need not be particularly accurate; it is used only to make
135 decisions about when a function is too big to inline. */
136 #define INSNS_PER_STMT (10)
138 /* Remap DECL during the copying of the BLOCK tree for the function. */
141 remap_decl (decl, id)
148 /* We only remap local variables in the current function. */
149 fn = VARRAY_TOP_TREE (id->fns);
150 if (! (*lang_hooks.tree_inlining.auto_var_in_fn_p) (decl, fn))
153 /* See if we have remapped this declaration. */
154 n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
155 /* If we didn't already have an equivalent for this declaration,
161 /* Make a copy of the variable or label. */
162 t = copy_decl_for_inlining (decl, fn,
163 VARRAY_TREE (id->fns, 0));
165 /* The decl T could be a dynamic array or other variable size type,
166 in which case some fields need to be remapped because they may
167 contain SAVE_EXPRs. */
168 if (TREE_TYPE (t) && TREE_CODE (TREE_TYPE (t)) == ARRAY_TYPE
169 && TYPE_DOMAIN (TREE_TYPE (t)))
171 TREE_TYPE (t) = copy_node (TREE_TYPE (t));
172 TYPE_DOMAIN (TREE_TYPE (t))
173 = copy_node (TYPE_DOMAIN (TREE_TYPE (t)));
174 walk_tree (&TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (t))),
175 copy_body_r, id, NULL);
178 #ifndef INLINER_FOR_JAVA
179 if (! DECL_NAME (t) && TREE_TYPE (t)
180 && (*lang_hooks.tree_inlining.anon_aggr_type_p) (TREE_TYPE (t)))
182 /* For a VAR_DECL of anonymous type, we must also copy the
183 member VAR_DECLS here and rechain the
184 DECL_ANON_UNION_ELEMS. */
188 for (src = DECL_ANON_UNION_ELEMS (t); src;
189 src = TREE_CHAIN (src))
191 tree member = remap_decl (TREE_VALUE (src), id);
193 if (TREE_PURPOSE (src))
195 members = tree_cons (NULL, member, members);
197 DECL_ANON_UNION_ELEMS (t) = nreverse (members);
199 #endif /* not INLINER_FOR_JAVA */
201 /* Remember it, so that if we encounter this local entity
202 again we can reuse this copy. */
203 n = splay_tree_insert (id->decl_map,
204 (splay_tree_key) decl,
205 (splay_tree_value) t);
208 return (tree) n->value;
211 #ifndef INLINER_FOR_JAVA
212 /* Copy the SCOPE_STMT_BLOCK associated with SCOPE_STMT to contain
213 remapped versions of the variables therein. And hook the new block
214 into the block-tree. If non-NULL, the DECLS are declarations to
215 add to use instead of the BLOCK_VARS in the old block. */
216 #else /* INLINER_FOR_JAVA */
217 /* Copy the BLOCK to contain remapped versions of the variables
218 therein. And hook the new block into the block-tree. */
219 #endif /* INLINER_FOR_JAVA */
222 #ifndef INLINER_FOR_JAVA
223 remap_block (scope_stmt, decls, id)
225 #else /* INLINER_FOR_JAVA */
226 remap_block (block, decls, id)
228 #endif /* INLINER_FOR_JAVA */
232 #ifndef INLINER_FOR_JAVA
233 /* We cannot do this in the cleanup for a TARGET_EXPR since we do
234 not know whether or not expand_expr will actually write out the
235 code we put there. If it does not, then we'll have more BLOCKs
236 than block-notes, and things will go awry. At some point, we
237 should make the back-end handle BLOCK notes in a tidier way,
238 without requiring a strict correspondence to the block-tree; then
239 this check can go. */
240 if (id->in_target_cleanup_p)
242 SCOPE_STMT_BLOCK (scope_stmt) = NULL_TREE;
246 /* If this is the beginning of a scope, remap the associated BLOCK. */
247 if (SCOPE_BEGIN_P (scope_stmt) && SCOPE_STMT_BLOCK (scope_stmt))
254 /* Make the new block. */
255 old_block = SCOPE_STMT_BLOCK (scope_stmt);
256 new_block = make_node (BLOCK);
257 TREE_USED (new_block) = TREE_USED (old_block);
258 BLOCK_ABSTRACT_ORIGIN (new_block) = old_block;
259 SCOPE_STMT_BLOCK (scope_stmt) = new_block;
261 /* Remap its variables. */
262 for (old_var = decls ? decls : BLOCK_VARS (old_block);
264 old_var = TREE_CHAIN (old_var))
268 /* Remap the variable. */
269 new_var = remap_decl (old_var, id);
270 /* If we didn't remap this variable, so we can't mess with
271 its TREE_CHAIN. If we remapped this variable to
272 something other than a declaration (say, if we mapped it
273 to a constant), then we must similarly omit any mention
275 if (!new_var || !DECL_P (new_var))
279 TREE_CHAIN (new_var) = BLOCK_VARS (new_block);
280 BLOCK_VARS (new_block) = new_var;
283 /* We put the BLOCK_VARS in reverse order; fix that now. */
284 BLOCK_VARS (new_block) = nreverse (BLOCK_VARS (new_block));
285 fn = VARRAY_TREE (id->fns, 0);
287 /* We're building a clone; DECL_INITIAL is still
288 error_mark_node, and current_binding_level is the parm
290 (*lang_hooks.decls.insert_block) (new_block);
293 /* Attach this new block after the DECL_INITIAL block for the
294 function into which this block is being inlined. In
295 rest_of_compilation we will straighten out the BLOCK tree. */
297 if (DECL_INITIAL (fn))
298 first_block = &BLOCK_CHAIN (DECL_INITIAL (fn));
300 first_block = &DECL_INITIAL (fn);
301 BLOCK_CHAIN (new_block) = *first_block;
302 *first_block = new_block;
304 /* Remember the remapped block. */
305 splay_tree_insert (id->decl_map,
306 (splay_tree_key) old_block,
307 (splay_tree_value) new_block);
309 /* If this is the end of a scope, set the SCOPE_STMT_BLOCK to be the
311 else if (SCOPE_END_P (scope_stmt) && SCOPE_STMT_BLOCK (scope_stmt))
315 /* Find this block in the table of remapped things. */
316 n = splay_tree_lookup (id->decl_map,
317 (splay_tree_key) SCOPE_STMT_BLOCK (scope_stmt));
320 SCOPE_STMT_BLOCK (scope_stmt) = (tree) n->value;
322 #else /* INLINER_FOR_JAVA */
328 /* Make the new block. */
330 new_block = make_node (BLOCK);
331 TREE_USED (new_block) = TREE_USED (old_block);
332 BLOCK_ABSTRACT_ORIGIN (new_block) = old_block;
333 BLOCK_SUBBLOCKS (new_block) = BLOCK_SUBBLOCKS (old_block);
334 TREE_SIDE_EFFECTS (new_block) = TREE_SIDE_EFFECTS (old_block);
335 TREE_TYPE (new_block) = TREE_TYPE (old_block);
338 /* Remap its variables. */
339 for (old_var = decls ? decls : BLOCK_VARS (old_block);
341 old_var = TREE_CHAIN (old_var))
345 /* All local class initialization flags go in the outermost
347 if (LOCAL_CLASS_INITIALIZATION_FLAG_P (old_var))
349 /* We may already have one. */
350 if (! splay_tree_lookup (id->decl_map, (splay_tree_key) old_var))
352 tree outermost_block;
353 new_var = remap_decl (old_var, id);
354 DECL_ABSTRACT_ORIGIN (new_var) = NULL;
355 outermost_block = DECL_SAVED_TREE (current_function_decl);
356 TREE_CHAIN (new_var) = BLOCK_VARS (outermost_block);
357 BLOCK_VARS (outermost_block) = new_var;
362 /* Remap the variable. */
363 new_var = remap_decl (old_var, id);
364 /* If we didn't remap this variable, so we can't mess with
365 its TREE_CHAIN. If we remapped this variable to
366 something other than a declaration (say, if we mapped it
367 to a constant), then we must similarly omit any mention
369 if (!new_var || !DECL_P (new_var))
373 TREE_CHAIN (new_var) = BLOCK_VARS (new_block);
374 BLOCK_VARS (new_block) = new_var;
377 /* We put the BLOCK_VARS in reverse order; fix that now. */
378 BLOCK_VARS (new_block) = nreverse (BLOCK_VARS (new_block));
379 fn = VARRAY_TREE (id->fns, 0);
380 /* Remember the remapped block. */
381 splay_tree_insert (id->decl_map,
382 (splay_tree_key) old_block,
383 (splay_tree_value) new_block);
384 #endif /* INLINER_FOR_JAVA */
387 #ifndef INLINER_FOR_JAVA
388 /* Copy the SCOPE_STMT pointed to by TP. */
391 copy_scope_stmt (tp, walk_subtrees, id)
398 /* Remember whether or not this statement was nullified. When
399 making a copy, copy_tree_r always sets SCOPE_NULLIFIED_P (and
400 doesn't copy the SCOPE_STMT_BLOCK) to free callers from having to
401 deal with copying BLOCKs if they do not wish to do so. */
402 block = SCOPE_STMT_BLOCK (*tp);
403 /* Copy (and replace) the statement. */
404 copy_tree_r (tp, walk_subtrees, NULL);
405 /* Restore the SCOPE_STMT_BLOCK. */
406 SCOPE_STMT_BLOCK (*tp) = block;
408 /* Remap the associated block. */
409 remap_block (*tp, NULL_TREE, id);
411 #endif /* not INLINER_FOR_JAVA */
413 /* Called from copy_body via walk_tree. DATA is really an
416 copy_body_r (tp, walk_subtrees, data)
425 id = (inline_data *) data;
426 fn = VARRAY_TOP_TREE (id->fns);
429 /* All automatic variables should have a DECL_CONTEXT indicating
430 what function they come from. */
431 if ((TREE_CODE (*tp) == VAR_DECL || TREE_CODE (*tp) == LABEL_DECL)
432 && DECL_NAMESPACE_SCOPE_P (*tp))
433 if (! DECL_EXTERNAL (*tp) && ! TREE_STATIC (*tp))
437 #ifdef INLINER_FOR_JAVA
438 if (TREE_CODE (*tp) == BLOCK)
439 remap_block (tp, NULL_TREE, id);
442 /* If this is a RETURN_STMT, change it into an EXPR_STMT and a
443 GOTO_STMT with the RET_LABEL as its target. */
444 #ifndef INLINER_FOR_JAVA
445 if (TREE_CODE (*tp) == RETURN_STMT && id->ret_label)
446 #else /* INLINER_FOR_JAVA */
447 if (TREE_CODE (*tp) == RETURN_EXPR && id->ret_label)
448 #endif /* INLINER_FOR_JAVA */
450 tree return_stmt = *tp;
453 /* Build the GOTO_STMT. */
454 #ifndef INLINER_FOR_JAVA
455 goto_stmt = build_stmt (GOTO_STMT, id->ret_label);
456 TREE_CHAIN (goto_stmt) = TREE_CHAIN (return_stmt);
457 GOTO_FAKE_P (goto_stmt) = 1;
458 #else /* INLINER_FOR_JAVA */
459 tree assignment = TREE_OPERAND (return_stmt, 0);
460 goto_stmt = build1 (GOTO_EXPR, void_type_node, id->ret_label);
461 TREE_SIDE_EFFECTS (goto_stmt) = 1;
462 #endif /* INLINER_FOR_JAVA */
464 /* If we're returning something, just turn that into an
465 assignment into the equivalent of the original
467 #ifndef INLINER_FOR_JAVA
468 if (RETURN_STMT_EXPR (return_stmt))
470 *tp = build_stmt (EXPR_STMT,
471 RETURN_STMT_EXPR (return_stmt));
472 STMT_IS_FULL_EXPR_P (*tp) = 1;
473 /* And then jump to the end of the function. */
474 TREE_CHAIN (*tp) = goto_stmt;
476 #else /* INLINER_FOR_JAVA */
479 copy_body_r (&assignment, walk_subtrees, data);
480 *tp = build (COMPOUND_EXPR, void_type_node, assignment, goto_stmt);
481 TREE_SIDE_EFFECTS (*tp) = 1;
483 #endif /* INLINER_FOR_JAVA */
484 /* If we're not returning anything just do the jump. */
488 /* Local variables and labels need to be replaced by equivalent
489 variables. We don't want to copy static variables; there's only
490 one of those, no matter how many times we inline the containing
492 else if ((*lang_hooks.tree_inlining.auto_var_in_fn_p) (*tp, fn))
496 /* Remap the declaration. */
497 new_decl = remap_decl (*tp, id);
500 /* Replace this variable with the copy. */
501 STRIP_TYPE_NOPS (new_decl);
505 else if (nonstatic_local_decl_p (*tp)
506 && DECL_CONTEXT (*tp) != VARRAY_TREE (id->fns, 0))
509 else if (TREE_CODE (*tp) == SAVE_EXPR)
510 remap_save_expr (tp, id->decl_map, VARRAY_TREE (id->fns, 0),
512 else if (TREE_CODE (*tp) == UNSAVE_EXPR)
513 /* UNSAVE_EXPRs should not be generated until expansion time. */
515 #ifndef INLINER_FOR_JAVA
516 /* For a SCOPE_STMT, we must copy the associated block so that we
517 can write out debugging information for the inlined variables. */
518 else if (TREE_CODE (*tp) == SCOPE_STMT && !id->in_target_cleanup_p)
519 copy_scope_stmt (tp, walk_subtrees, id);
520 #else /* INLINER_FOR_JAVA */
521 else if (TREE_CODE (*tp) == LABELED_BLOCK_EXPR)
523 /* We need a new copy of this labeled block; the EXIT_BLOCK_EXPR
524 will refer to it, so save a copy ready for remapping. We
525 save it in the decl_map, although it isn't a decl. */
526 tree new_block = copy_node (*tp);
527 splay_tree_insert (id->decl_map,
528 (splay_tree_key) *tp,
529 (splay_tree_value) new_block);
532 else if (TREE_CODE (*tp) == EXIT_BLOCK_EXPR)
535 = splay_tree_lookup (id->decl_map,
536 (splay_tree_key) TREE_OPERAND (*tp, 0));
537 /* We _must_ have seen the enclosing LABELED_BLOCK_EXPR. */
540 *tp = copy_node (*tp);
541 TREE_OPERAND (*tp, 0) = (tree) n->value;
543 #endif /* INLINER_FOR_JAVA */
544 /* Otherwise, just copy the node. Note that copy_tree_r already
545 knows not to copy VAR_DECLs, etc., so this is safe. */
548 copy_tree_r (tp, walk_subtrees, NULL);
550 /* The copied TARGET_EXPR has never been expanded, even if the
551 original node was expanded already. */
552 if (TREE_CODE (*tp) == TARGET_EXPR && TREE_OPERAND (*tp, 3))
554 TREE_OPERAND (*tp, 1) = TREE_OPERAND (*tp, 3);
555 TREE_OPERAND (*tp, 3) = NULL_TREE;
557 else if (TREE_CODE (*tp) == MODIFY_EXPR
558 && TREE_OPERAND (*tp, 0) == TREE_OPERAND (*tp, 1)
559 && ((*lang_hooks.tree_inlining.auto_var_in_fn_p)
560 (TREE_OPERAND (*tp, 0), fn)))
562 /* Some assignments VAR = VAR; don't generate any rtl code
563 and thus don't count as variable modification. Avoid
564 keeping bogosities like 0 = 0. */
565 tree decl = TREE_OPERAND (*tp, 0), value;
568 n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
571 value = (tree) n->value;
572 STRIP_TYPE_NOPS (value);
573 if (TREE_CONSTANT (value) || TREE_READONLY_DECL_P (value))
579 /* Keep iterating. */
583 /* Make a copy of the body of FN so that it can be inserted inline in
592 body = DECL_SAVED_TREE (VARRAY_TOP_TREE (id->fns));
593 walk_tree (&body, copy_body_r, id, NULL);
598 /* Generate code to initialize the parameters of the function at the
599 top of the stack in ID from the ARGS (presented as a TREE_LIST). */
602 #ifndef INLINER_FOR_JAVA
603 initialize_inlined_parameters (id, args, fn)
604 #else /* INLINER_FOR_JAVA */
605 initialize_inlined_parameters (id, args, fn, block)
606 #endif /* INLINER_FOR_JAVA */
610 #ifdef INLINER_FOR_JAVA
612 #endif /* INLINER_FOR_JAVA */
618 #ifdef INLINER_FOR_JAVA
619 tree vars = NULL_TREE;
620 #endif /* INLINER_FOR_JAVA */
622 /* Figure out what the parameters are. */
623 parms = DECL_ARGUMENTS (fn);
625 /* Start with no initializations whatsoever. */
626 init_stmts = NULL_TREE;
628 /* Loop through the parameter declarations, replacing each with an
629 equivalent VAR_DECL, appropriately initialized. */
630 for (p = parms, a = args; p;
631 a = a ? TREE_CHAIN (a) : a, p = TREE_CHAIN (p))
633 #ifndef INLINER_FOR_JAVA
636 #endif /* not INLINER_FOR_JAVA */
641 /* Find the initializer. */
642 value = (*lang_hooks.tree_inlining.convert_parm_for_inlining)
643 (p, a ? TREE_VALUE (a) : NULL_TREE, fn);
645 /* If the parameter is never assigned to, we may not need to
646 create a new variable here at all. Instead, we may be able
647 to just use the argument value. */
648 if (TREE_READONLY (p)
649 && !TREE_ADDRESSABLE (p)
650 && value && !TREE_SIDE_EFFECTS (value))
652 /* Simplify the value, if possible. */
653 value = fold (DECL_P (value) ? decl_constant_value (value) : value);
655 /* We can't risk substituting complex expressions. They
656 might contain variables that will be assigned to later.
657 Theoretically, we could check the expression to see if
658 all of the variables that determine its value are
659 read-only, but we don't bother. */
660 if (TREE_CONSTANT (value) || TREE_READONLY_DECL_P (value))
662 /* If this is a declaration, wrap it a NOP_EXPR so that
663 we don't try to put the VALUE on the list of
666 value = build1 (NOP_EXPR, TREE_TYPE (value), value);
668 splay_tree_insert (id->decl_map,
670 (splay_tree_value) value);
675 /* Make an equivalent VAR_DECL. */
676 var = copy_decl_for_inlining (p, fn, VARRAY_TREE (id->fns, 0));
678 /* See if the frontend wants to pass this by invisible reference. If
679 so, our new VAR_DECL will have REFERENCE_TYPE, and we need to
680 replace uses of the PARM_DECL with dereferences. */
681 if (TREE_TYPE (var) != TREE_TYPE (p)
682 && POINTER_TYPE_P (TREE_TYPE (var))
683 && TREE_TYPE (TREE_TYPE (var)) == TREE_TYPE (p))
684 var_sub = build1 (INDIRECT_REF, TREE_TYPE (p), var);
688 /* Register the VAR_DECL as the equivalent for the PARM_DECL;
689 that way, when the PARM_DECL is encountered, it will be
690 automatically replaced by the VAR_DECL. */
691 splay_tree_insert (id->decl_map,
693 (splay_tree_value) var_sub);
695 /* Declare this new variable. */
696 #ifndef INLINER_FOR_JAVA
697 init_stmt = build_stmt (DECL_STMT, var);
698 TREE_CHAIN (init_stmt) = init_stmts;
699 init_stmts = init_stmt;
700 #else /* INLINER_FOR_JAVA */
701 TREE_CHAIN (var) = vars;
703 #endif /* INLINER_FOR_JAVA */
705 /* Initialize this VAR_DECL from the equivalent argument. If
706 the argument is an object, created via a constructor or copy,
707 this will not result in an extra copy: the TARGET_EXPR
708 representing the argument will be bound to VAR, and the
709 object will be constructed in VAR. */
710 if (! TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (p)))
711 #ifndef INLINER_FOR_JAVA
712 DECL_INITIAL (var) = value;
715 /* Even if P was TREE_READONLY, the new VAR should not be.
716 In the original code, we would have constructed a
717 temporary, and then the function body would have never
718 changed the value of P. However, now, we will be
719 constructing VAR directly. The constructor body may
720 change its value multiple times as it is being
721 constructed. Therefore, it must not be TREE_READONLY;
722 the back-end assumes that TREE_READONLY variable is
723 assigned to only once. */
724 TREE_READONLY (var) = 0;
726 /* Build a run-time initialization. */
727 init_stmt = build_stmt (EXPR_STMT,
728 build (INIT_EXPR, TREE_TYPE (p),
730 /* Add this initialization to the list. Note that we want the
731 declaration *after* the initialization because we are going
732 to reverse all the initialization statements below. */
733 TREE_CHAIN (init_stmt) = init_stmts;
734 init_stmts = init_stmt;
737 /* See if we need to clean up the declaration. */
738 cleanup = (*lang_hooks.maybe_build_cleanup) (var);
742 /* Build the cleanup statement. */
743 cleanup_stmt = build_stmt (CLEANUP_STMT, var, cleanup);
744 /* Add it to the *front* of the list; the list will be
746 TREE_CHAIN (cleanup_stmt) = init_stmts;
747 init_stmts = cleanup_stmt;
749 #else /* INLINER_FOR_JAVA */
751 tree assignment = build (MODIFY_EXPR, TREE_TYPE (p), var, value);
752 init_stmts = add_stmt_to_compound (init_stmts, TREE_TYPE (p),
757 /* Java objects don't ever need constructing when being
758 passed as arguments because only call by reference is
762 #endif /* INLINER_FOR_JAVA */
765 #ifndef INLINER_FOR_JAVA
766 /* Evaluate trailing arguments. */
767 for (; a; a = TREE_CHAIN (a))
770 tree value = TREE_VALUE (a);
772 if (! value || ! TREE_SIDE_EFFECTS (value))
775 init_stmt = build_stmt (EXPR_STMT, value);
776 TREE_CHAIN (init_stmt) = init_stmts;
777 init_stmts = init_stmt;
780 /* The initialization statements have been built up in reverse
781 order. Straighten them out now. */
782 return nreverse (init_stmts);
783 #else /* INLINER_FOR_JAVA */
784 BLOCK_VARS (block) = nreverse (vars);
786 #endif /* INLINER_FOR_JAVA */
789 /* Declare a return variable to replace the RESULT_DECL for the
790 function we are calling. An appropriate DECL_STMT is returned.
791 The USE_STMT is filled in to contain a use of the declaration to
792 indicate the return value of the function. */
794 #ifndef INLINER_FOR_JAVA
796 declare_return_variable (id, return_slot_addr, use_stmt)
797 struct inline_data *id;
798 tree return_slot_addr;
800 #else /* INLINER_FOR_JAVA */
802 declare_return_variable (id, return_slot_addr, var)
803 struct inline_data *id;
804 tree return_slot_addr;
806 #endif /* INLINER_FOR_JAVA */
808 tree fn = VARRAY_TOP_TREE (id->fns);
809 tree result = DECL_RESULT (fn);
810 #ifndef INLINER_FOR_JAVA
812 #endif /* not INLINER_FOR_JAVA */
813 int need_return_decl = 1;
815 /* We don't need to do anything for functions that don't return
817 if (!result || VOID_TYPE_P (TREE_TYPE (result)))
819 #ifndef INLINER_FOR_JAVA
820 *use_stmt = NULL_TREE;
821 #else /* INLINER_FOR_JAVA */
823 #endif /* INLINER_FOR_JAVA */
827 #ifndef INLINER_FOR_JAVA
828 var = ((*lang_hooks.tree_inlining.copy_res_decl_for_inlining)
829 (result, fn, VARRAY_TREE (id->fns, 0), id->decl_map,
830 &need_return_decl, return_slot_addr));
832 /* Register the VAR_DECL as the equivalent for the RESULT_DECL; that
833 way, when the RESULT_DECL is encountered, it will be
834 automatically replaced by the VAR_DECL. */
835 splay_tree_insert (id->decl_map,
836 (splay_tree_key) result,
837 (splay_tree_value) var);
839 /* Build the USE_STMT. If the return type of the function was
840 promoted, convert it back to the expected type. */
841 if (TREE_TYPE (var) == TREE_TYPE (TREE_TYPE (fn)))
842 *use_stmt = build_stmt (EXPR_STMT, var);
844 *use_stmt = build_stmt (EXPR_STMT,
845 build1 (NOP_EXPR, TREE_TYPE (TREE_TYPE (fn)),
847 TREE_ADDRESSABLE (*use_stmt) = 1;
849 /* Build the declaration statement if FN does not return an
851 if (need_return_decl)
852 return build_stmt (DECL_STMT, var);
853 #else /* INLINER_FOR_JAVA */
854 *var = ((*lang_hooks.tree_inlining.copy_res_decl_for_inlining)
855 (result, fn, VARRAY_TREE (id->fns, 0), id->decl_map,
856 &need_return_decl, return_slot_addr));
858 splay_tree_insert (id->decl_map,
859 (splay_tree_key) result,
860 (splay_tree_value) *var);
861 DECL_IGNORED_P (*var) = 1;
862 if (need_return_decl)
864 #endif /* INLINER_FOR_JAVA */
865 /* If FN does return an aggregate, there's no need to declare the
866 return variable; we're using a variable in our caller's frame. */
871 /* Returns nonzero if a function can be inlined as a tree. */
874 tree_inlinable_function_p (fn)
877 return inlinable_function_p (fn, NULL);
880 /* If *TP is possibly call to alloca, return nonzero. */
882 find_alloca_call_1 (tp, walk_subtrees, data)
884 int *walk_subtrees ATTRIBUTE_UNUSED;
885 void *data ATTRIBUTE_UNUSED;
887 if (alloca_call_p (*tp))
892 /* Return subexpression representing possible alloca call, if any. */
894 find_alloca_call (exp)
897 return walk_tree (&exp, find_alloca_call_1, NULL, NULL);
901 find_builtin_longjmp_call_1 (tp, walk_subtrees, data)
903 int *walk_subtrees ATTRIBUTE_UNUSED;
904 void *data ATTRIBUTE_UNUSED;
906 tree exp = *tp, decl;
908 if (TREE_CODE (exp) == CALL_EXPR
909 && TREE_CODE (TREE_OPERAND (exp, 0)) == ADDR_EXPR
910 && (decl = TREE_OPERAND (TREE_OPERAND (exp, 0), 0),
911 TREE_CODE (decl) == FUNCTION_DECL)
912 && DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL
913 && DECL_FUNCTION_CODE (decl) == BUILT_IN_LONGJMP)
920 find_builtin_longjmp_call (exp)
923 return walk_tree (&exp, find_builtin_longjmp_call_1, NULL, NULL);
926 /* Returns nonzero if FN is a function that can be inlined into the
927 inlining context ID_. If ID_ is NULL, check whether the function
928 can be inlined at all. */
931 inlinable_function_p (fn, id)
938 /* If we've already decided this function shouldn't be inlined,
939 there's no need to check again. */
940 if (DECL_UNINLINABLE (fn))
943 /* Assume it is not inlinable. */
946 /* The number of instructions (estimated) of current function. */
947 currfn_insns = DECL_NUM_STMTS (fn) * INSNS_PER_STMT;
949 /* If we're not inlining things, then nothing is inlinable. */
950 if (! flag_inline_trees)
952 /* If we're not inlining all functions and the function was not
953 declared `inline', we don't inline it. Don't think of
954 disregarding DECL_INLINE when flag_inline_trees == 2; it's the
955 front-end that must set DECL_INLINE in this case, because
956 dwarf2out loses if a function is inlined that doesn't have
958 else if (! DECL_INLINE (fn))
960 /* We can't inline functions that are too big. Only allow a single
961 function to be of MAX_INLINE_INSNS_SINGLE size. Make special
962 allowance for extern inline functions, though. */
963 else if (! (*lang_hooks.tree_inlining.disregard_inline_limits) (fn)
964 && currfn_insns > MAX_INLINE_INSNS_SINGLE)
966 /* We can't inline functions that call __builtin_longjmp at all.
967 The non-local goto machenery really requires the destination
968 be in a different function. If we allow the function calling
969 __builtin_longjmp to be inlined into the function calling
970 __builtin_setjmp, Things will Go Awry. */
971 /* ??? Need front end help to identify "regular" non-local goto. */
972 else if (find_builtin_longjmp_call (DECL_SAVED_TREE (fn)))
974 /* Refuse to inline alloca call unless user explicitly forced so as this may
975 change program's memory overhead drastically when the function using alloca
976 is called in loop. In GCC present in SPEC2000 inlining into schedule_block
977 cause it to require 2GB of ram instead of 256MB. */
978 else if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)) == NULL
979 && find_alloca_call (DECL_SAVED_TREE (fn)))
981 /* All is well. We can inline this function. Traditionally, GCC
982 has refused to inline functions using alloca, or functions whose
983 values are returned in a PARALLEL, and a few other such obscure
984 conditions. We are not equally constrained at the tree level. */
988 /* Squirrel away the result so that we don't have to check again. */
989 DECL_UNINLINABLE (fn) = ! inlinable;
991 /* In case we don't disregard the inlining limits and we basically
992 can inline this function, investigate further. */
993 if (! (*lang_hooks.tree_inlining.disregard_inline_limits) (fn)
996 int sum_insns = (id ? id->inlined_stmts : 0) * INSNS_PER_STMT
998 /* In the extreme case that we have exceeded the recursive inlining
999 limit by a huge factor (128), we just say no. Should not happen
1001 if (sum_insns > MAX_INLINE_INSNS * 128)
1003 /* If we did not hit the extreme limit, we use a linear function
1004 with slope -1/MAX_INLINE_SLOPE to exceedingly decrease the
1005 allowable size. We always allow a size of MIN_INLINE_INSNS
1007 else if ((sum_insns > MAX_INLINE_INSNS)
1008 && (currfn_insns > MIN_INLINE_INSNS))
1010 int max_curr = MAX_INLINE_INSNS_SINGLE
1011 - (sum_insns - MAX_INLINE_INSNS) / MAX_INLINE_SLOPE;
1012 if (currfn_insns > max_curr)
1017 if (inlinable && (*lang_hooks.tree_inlining.cannot_inline_tree_fn) (&fn))
1020 /* If we don't have the function body available, we can't inline
1022 if (! DECL_SAVED_TREE (fn))
1025 /* Check again, language hooks may have modified it. */
1026 if (! inlinable || DECL_UNINLINABLE (fn))
1029 /* Don't do recursive inlining, either. We don't record this in
1030 DECL_UNINLINABLE; we may be able to inline this function later. */
1035 for (i = 0; i < VARRAY_ACTIVE_SIZE (id->fns); ++i)
1036 if (VARRAY_TREE (id->fns, i) == fn)
1039 if (DECL_INLINED_FNS (fn))
1042 tree inlined_fns = DECL_INLINED_FNS (fn);
1044 for (j = 0; j < TREE_VEC_LENGTH (inlined_fns); ++j)
1045 if (TREE_VEC_ELT (inlined_fns, j) == VARRAY_TREE (id->fns, 0))
1050 /* Return the result. */
1054 /* If *TP is a CALL_EXPR, replace it with its inline expansion. */
1057 expand_call_inline (tp, walk_subtrees, data)
1066 #ifndef INLINER_FOR_JAVA
1070 #else /* INLINER_FOR_JAVA */
1072 #endif /* INLINER_FOR_JAVA */
1078 tree return_slot_addr;
1080 /* See what we've got. */
1081 id = (inline_data *) data;
1084 /* Recurse, but letting recursive invocations know that we are
1085 inside the body of a TARGET_EXPR. */
1086 if (TREE_CODE (*tp) == TARGET_EXPR)
1088 #ifndef INLINER_FOR_JAVA
1089 int i, len = first_rtl_op (TARGET_EXPR);
1091 /* We're walking our own subtrees. */
1094 /* Actually walk over them. This loop is the body of
1095 walk_trees, omitting the case where the TARGET_EXPR
1096 itself is handled. */
1097 for (i = 0; i < len; ++i)
1100 ++id->in_target_cleanup_p;
1101 walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data,
1104 --id->in_target_cleanup_p;
1108 #else /* INLINER_FOR_JAVA */
1110 #endif /* INLINER_FOR_JAVA */
1114 /* Because types were not copied in copy_body, CALL_EXPRs beneath
1115 them should not be expanded. This can happen if the type is a
1116 dynamic array type, for example. */
1119 /* From here on, we're only interested in CALL_EXPRs. */
1120 if (TREE_CODE (t) != CALL_EXPR)
1123 /* First, see if we can figure out what function is being called.
1124 If we cannot, then there is no hope of inlining the function. */
1125 fn = get_callee_fndecl (t);
1129 /* If fn is a declaration of a function in a nested scope that was
1130 globally declared inline, we don't set its DECL_INITIAL.
1131 However, we can't blindly follow DECL_ABSTRACT_ORIGIN because the
1132 C++ front-end uses it for cdtors to refer to their internal
1133 declarations, that are not real functions. Fortunately those
1134 don't have trees to be saved, so we can tell by checking their
1136 if (! DECL_INITIAL (fn)
1137 && DECL_ABSTRACT_ORIGIN (fn)
1138 && DECL_SAVED_TREE (DECL_ABSTRACT_ORIGIN (fn)))
1139 fn = DECL_ABSTRACT_ORIGIN (fn);
1141 /* Don't try to inline functions that are not well-suited to
1143 if (!inlinable_function_p (fn, id))
1146 if (! (*lang_hooks.tree_inlining.start_inlining) (fn))
1149 /* Set the current filename and line number to the function we are
1150 inlining so that when we create new _STMT nodes here they get
1151 line numbers corresponding to the function we are calling. We
1152 wrap the whole inlined body in an EXPR_WITH_FILE_AND_LINE as well
1153 because individual statements don't record the filename. */
1154 push_srcloc (DECL_SOURCE_FILE (fn), DECL_SOURCE_LINE (fn));
1156 #ifndef INLINER_FOR_JAVA
1157 /* Build a statement-expression containing code to initialize the
1158 arguments, the actual inline expansion of the body, and a label
1159 for the return statements within the function to jump to. The
1160 type of the statement expression is the return type of the
1162 expr = build1 (STMT_EXPR, TREE_TYPE (TREE_TYPE (fn)), make_node (COMPOUND_STMT));
1163 /* There is no scope associated with the statement-expression. */
1164 STMT_EXPR_NO_SCOPE (expr) = 1;
1165 stmt = STMT_EXPR_STMT (expr);
1166 #else /* INLINER_FOR_JAVA */
1167 /* Build a block containing code to initialize the arguments, the
1168 actual inline expansion of the body, and a label for the return
1169 statements within the function to jump to. The type of the
1170 statement expression is the return type of the function call. */
1172 expr = build (BLOCK, TREE_TYPE (TREE_TYPE (fn)), stmt);
1173 #endif /* INLINER_FOR_JAVA */
1175 /* Local declarations will be replaced by their equivalents in this
1178 id->decl_map = splay_tree_new (splay_tree_compare_pointers,
1181 /* Initialize the parameters. */
1182 args = TREE_OPERAND (t, 1);
1183 return_slot_addr = NULL_TREE;
1184 if (CALL_EXPR_HAS_RETURN_SLOT_ADDR (t))
1186 return_slot_addr = TREE_VALUE (args);
1187 args = TREE_CHAIN (args);
1190 #ifndef INLINER_FOR_JAVA
1191 arg_inits = initialize_inlined_parameters (id, args, fn);
1192 /* Expand any inlined calls in the initializers. Do this before we
1193 push FN on the stack of functions we are inlining; we want to
1194 inline calls to FN that appear in the initializers for the
1196 expand_calls_inline (&arg_inits, id);
1197 /* And add them to the tree. */
1198 COMPOUND_BODY (stmt) = chainon (COMPOUND_BODY (stmt), arg_inits);
1199 #else /* INLINER_FOR_JAVA */
1200 arg_inits = initialize_inlined_parameters (id, args, fn, expr);
1203 /* Expand any inlined calls in the initializers. Do this before we
1204 push FN on the stack of functions we are inlining; we want to
1205 inline calls to FN that appear in the initializers for the
1207 expand_calls_inline (&arg_inits, id);
1209 /* And add them to the tree. */
1210 BLOCK_EXPR_BODY (expr) = add_stmt_to_compound (BLOCK_EXPR_BODY (expr),
1211 TREE_TYPE (arg_inits),
1214 #endif /* INLINER_FOR_JAVA */
1216 /* Record the function we are about to inline so that we can avoid
1217 recursing into it. */
1218 VARRAY_PUSH_TREE (id->fns, fn);
1220 /* Record the function we are about to inline if optimize_function
1221 has not been called on it yet and we don't have it in the list. */
1222 if (! DECL_INLINED_FNS (fn))
1226 for (i = VARRAY_ACTIVE_SIZE (id->inlined_fns) - 1; i >= 0; i--)
1227 if (VARRAY_TREE (id->inlined_fns, i) == fn)
1230 VARRAY_PUSH_TREE (id->inlined_fns, fn);
1233 /* Return statements in the function body will be replaced by jumps
1234 to the RET_LABEL. */
1235 id->ret_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
1236 DECL_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0);
1238 if (! DECL_INITIAL (fn)
1239 || TREE_CODE (DECL_INITIAL (fn)) != BLOCK)
1242 #ifndef INLINER_FOR_JAVA
1243 /* Create a block to put the parameters in. We have to do this
1244 after the parameters have been remapped because remapping
1245 parameters is different from remapping ordinary variables. */
1246 scope_stmt = build_stmt (SCOPE_STMT, DECL_INITIAL (fn));
1247 SCOPE_BEGIN_P (scope_stmt) = 1;
1248 SCOPE_NO_CLEANUPS_P (scope_stmt) = 1;
1249 remap_block (scope_stmt, DECL_ARGUMENTS (fn), id);
1250 TREE_CHAIN (scope_stmt) = COMPOUND_BODY (stmt);
1251 COMPOUND_BODY (stmt) = scope_stmt;
1253 /* Tell the debugging backends that this block represents the
1254 outermost scope of the inlined function. */
1255 if (SCOPE_STMT_BLOCK (scope_stmt))
1256 BLOCK_ABSTRACT_ORIGIN (SCOPE_STMT_BLOCK (scope_stmt)) = DECL_ORIGIN (fn);
1258 /* Declare the return variable for the function. */
1259 COMPOUND_BODY (stmt)
1260 = chainon (COMPOUND_BODY (stmt),
1261 declare_return_variable (id, return_slot_addr, &use_stmt));
1262 #else /* INLINER_FOR_JAVA */
1264 /* Declare the return variable for the function. */
1265 tree decl = declare_return_variable (id, return_slot_addr, &retvar);
1268 tree *next = &BLOCK_VARS (expr);
1270 next = &TREE_CHAIN (*next);
1274 #endif /* INLINER_FOR_JAVA */
1276 /* After we've initialized the parameters, we insert the body of the
1278 #ifndef INLINER_FOR_JAVA
1279 inlined_body = &COMPOUND_BODY (stmt);
1280 while (*inlined_body)
1281 inlined_body = &TREE_CHAIN (*inlined_body);
1282 *inlined_body = copy_body (id);
1283 #else /* INLINER_FOR_JAVA */
1286 java_inlining_map_static_initializers (fn, id->decl_map);
1287 new_body = copy_body (id);
1288 TREE_TYPE (new_body) = TREE_TYPE (TREE_TYPE (fn));
1289 BLOCK_EXPR_BODY (expr)
1290 = add_stmt_to_compound (BLOCK_EXPR_BODY (expr),
1291 TREE_TYPE (new_body), new_body);
1292 inlined_body = &BLOCK_EXPR_BODY (expr);
1294 #endif /* INLINER_FOR_JAVA */
1296 /* After the body of the function comes the RET_LABEL. This must come
1297 before we evaluate the returned value below, because that evaluation
1298 may cause RTL to be generated. */
1299 #ifndef INLINER_FOR_JAVA
1300 COMPOUND_BODY (stmt)
1301 = chainon (COMPOUND_BODY (stmt),
1302 build_stmt (LABEL_STMT, id->ret_label));
1303 #else /* INLINER_FOR_JAVA */
1305 tree label = build1 (LABEL_EXPR, void_type_node, id->ret_label);
1306 BLOCK_EXPR_BODY (expr)
1307 = add_stmt_to_compound (BLOCK_EXPR_BODY (expr), void_type_node, label);
1308 TREE_SIDE_EFFECTS (label) = TREE_SIDE_EFFECTS (t);
1310 #endif /* INLINER_FOR_JAVA */
1312 /* Finally, mention the returned value so that the value of the
1313 statement-expression is the returned value of the function. */
1314 #ifndef INLINER_FOR_JAVA
1315 COMPOUND_BODY (stmt) = chainon (COMPOUND_BODY (stmt), use_stmt);
1317 /* Close the block for the parameters. */
1318 scope_stmt = build_stmt (SCOPE_STMT, DECL_INITIAL (fn));
1319 SCOPE_NO_CLEANUPS_P (scope_stmt) = 1;
1320 remap_block (scope_stmt, NULL_TREE, id);
1321 COMPOUND_BODY (stmt)
1322 = chainon (COMPOUND_BODY (stmt), scope_stmt);
1323 #else /* INLINER_FOR_JAVA */
1326 /* Mention the retvar. If the return type of the function was
1327 promoted, convert it back to the expected type. */
1328 if (TREE_TYPE (TREE_TYPE (fn)) != TREE_TYPE (retvar))
1329 retvar = build1 (NOP_EXPR, TREE_TYPE (TREE_TYPE (fn)), retvar);
1330 BLOCK_EXPR_BODY (expr)
1331 = add_stmt_to_compound (BLOCK_EXPR_BODY (expr),
1332 TREE_TYPE (retvar), retvar);
1335 java_inlining_merge_static_initializers (fn, id->decl_map);
1336 #endif /* INLINER_FOR_JAVA */
1339 splay_tree_delete (id->decl_map);
1342 /* The new expression has side-effects if the old one did. */
1343 TREE_SIDE_EFFECTS (expr) = TREE_SIDE_EFFECTS (t);
1345 /* Replace the call by the inlined body. Wrap it in an
1346 EXPR_WITH_FILE_LOCATION so that we'll get debugging line notes
1347 pointing to the right place. */
1348 #ifndef INLINER_FOR_JAVA
1349 chain = TREE_CHAIN (*tp);
1350 *tp = build_expr_wfl (expr, DECL_SOURCE_FILE (fn), DECL_SOURCE_LINE (fn),
1352 #else /* INLINER_FOR_JAVA */
1353 *tp = build_expr_wfl (expr, DECL_SOURCE_FILE (fn),
1354 DECL_SOURCE_LINE_FIRST(fn),
1356 #endif /* INLINER_FOR_JAVA */
1357 EXPR_WFL_EMIT_LINE_NOTE (*tp) = 1;
1358 #ifndef INLINER_FOR_JAVA
1359 TREE_CHAIN (*tp) = chain;
1360 #endif /* not INLINER_FOR_JAVA */
1363 /* If the value of the new expression is ignored, that's OK. We
1364 don't warn about this for CALL_EXPRs, so we shouldn't warn about
1365 the equivalent inlined version either. */
1366 TREE_USED (*tp) = 1;
1368 /* Our function now has more statements than it did before. */
1369 DECL_NUM_STMTS (VARRAY_TREE (id->fns, 0)) += DECL_NUM_STMTS (fn);
1370 /* For accounting, subtract one for the saved call/ret. */
1371 id->inlined_stmts += DECL_NUM_STMTS (fn) - 1;
1373 /* Update callgraph if needed. */
1374 if (id->decl && flag_unit_at_a_time)
1376 cgraph_remove_call (id->decl, fn);
1377 cgraph_create_edges (id->decl, *inlined_body);
1380 /* Recurse into the body of the just inlined function. */
1381 expand_calls_inline (inlined_body, id);
1382 VARRAY_POP (id->fns);
1384 /* If we've returned to the top level, clear out the record of how
1385 much inlining has been done. */
1386 if (VARRAY_ACTIVE_SIZE (id->fns) == id->first_inlined_fn)
1387 id->inlined_stmts = 0;
1389 /* Don't walk into subtrees. We've already handled them above. */
1392 (*lang_hooks.tree_inlining.end_inlining) (fn);
1394 /* Keep iterating. */
1397 /* Walk over the entire tree *TP, replacing CALL_EXPRs with inline
1398 expansions as appropriate. */
1401 expand_calls_inline (tp, id)
1405 /* Search through *TP, replacing all calls to inline functions by
1406 appropriate equivalents. Use walk_tree in no-duplicates mode
1407 to avoid exponential time complexity. (We can't just use
1408 walk_tree_without_duplicates, because of the special TARGET_EXPR
1409 handling in expand_calls. The hash table is set up in
1410 optimize_function. */
1411 walk_tree (tp, expand_call_inline, id, id->tree_pruner);
1414 /* Expand calls to inline functions in the body of FN. */
1417 optimize_inline_calls (fn)
1424 memset (&id, 0, sizeof (id));
1427 /* Don't allow recursion into FN. */
1428 VARRAY_TREE_INIT (id.fns, 32, "fns");
1429 VARRAY_PUSH_TREE (id.fns, fn);
1430 /* Or any functions that aren't finished yet. */
1431 prev_fn = NULL_TREE;
1432 if (current_function_decl)
1434 VARRAY_PUSH_TREE (id.fns, current_function_decl);
1435 prev_fn = current_function_decl;
1438 prev_fn = ((*lang_hooks.tree_inlining.add_pending_fn_decls)
1439 (&id.fns, prev_fn));
1441 /* Create the list of functions this call will inline. */
1442 VARRAY_TREE_INIT (id.inlined_fns, 32, "inlined_fns");
1444 /* Keep track of the low-water mark, i.e., the point where the first
1445 real inlining is represented in ID.FNS. */
1446 id.first_inlined_fn = VARRAY_ACTIVE_SIZE (id.fns);
1448 /* Replace all calls to inline functions with the bodies of those
1450 id.tree_pruner = htab_create (37, htab_hash_pointer,
1451 htab_eq_pointer, NULL);
1452 expand_calls_inline (&DECL_SAVED_TREE (fn), &id);
1455 htab_delete (id.tree_pruner);
1456 if (DECL_LANG_SPECIFIC (fn))
1458 tree ifn = make_tree_vec (VARRAY_ACTIVE_SIZE (id.inlined_fns));
1460 if (VARRAY_ACTIVE_SIZE (id.inlined_fns))
1461 memcpy (&TREE_VEC_ELT (ifn, 0), &VARRAY_TREE (id.inlined_fns, 0),
1462 VARRAY_ACTIVE_SIZE (id.inlined_fns) * sizeof (tree));
1463 DECL_INLINED_FNS (fn) = ifn;
1467 /* FN is a function that has a complete body, and CLONE is a function
1468 whose body is to be set to a copy of FN, mapping argument
1469 declarations according to the ARG_MAP splay_tree. */
1472 clone_body (clone, fn, arg_map)
1478 /* Clone the body, as if we were making an inline call. But, remap
1479 the parameters in the callee to the parameters of caller. If
1480 there's an in-charge parameter, map it to an appropriate
1482 memset (&id, 0, sizeof (id));
1483 VARRAY_TREE_INIT (id.fns, 2, "fns");
1484 VARRAY_PUSH_TREE (id.fns, clone);
1485 VARRAY_PUSH_TREE (id.fns, fn);
1486 id.decl_map = (splay_tree)arg_map;
1488 /* Cloning is treated slightly differently from inlining. Set
1489 CLONING_P so that it's clear which operation we're performing. */
1490 id.cloning_p = true;
1492 /* Actually copy the body. */
1493 TREE_CHAIN (DECL_SAVED_TREE (clone)) = copy_body (&id);
1496 /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.
1497 FUNC is called with the DATA and the address of each sub-tree. If
1498 FUNC returns a non-NULL value, the traversal is aborted, and the
1499 value returned by FUNC is returned. If HTAB is non-NULL it is used
1500 to record the nodes visited, and to avoid visiting a node more than
1504 walk_tree (tp, func, data, htab_)
1510 htab_t htab = (htab_t) htab_;
1511 enum tree_code code;
1515 #define WALK_SUBTREE(NODE) \
1518 result = walk_tree (&(NODE), func, data, htab); \
1524 #define WALK_SUBTREE_TAIL(NODE) \
1528 goto tail_recurse; \
1533 /* Skip empty subtrees. */
1541 /* Don't walk the same tree twice, if the user has requested
1542 that we avoid doing so. */
1543 slot = htab_find_slot (htab, *tp, INSERT);
1549 /* Call the function. */
1551 result = (*func) (tp, &walk_subtrees, data);
1553 /* If we found something, return it. */
1557 code = TREE_CODE (*tp);
1559 #ifndef INLINER_FOR_JAVA
1560 /* Even if we didn't, FUNC may have decided that there was nothing
1561 interesting below this point in the tree. */
1564 if (statement_code_p (code) || code == TREE_LIST
1565 || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp))
1566 /* But we still need to check our siblings. */
1567 WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
1572 /* Handle common cases up front. */
1573 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
1574 || TREE_CODE_CLASS (code) == 'r'
1575 || TREE_CODE_CLASS (code) == 's')
1576 #else /* INLINER_FOR_JAVA */
1577 if (code != EXIT_BLOCK_EXPR
1578 && code != SAVE_EXPR
1579 && (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
1580 || TREE_CODE_CLASS (code) == 'r'
1581 || TREE_CODE_CLASS (code) == 's'))
1582 #endif /* INLINER_FOR_JAVA */
1586 #ifndef INLINER_FOR_JAVA
1587 /* Set lineno here so we get the right instantiation context
1588 if we call instantiate_decl from inlinable_function_p. */
1589 if (statement_code_p (code) && !STMT_LINENO_FOR_FN_P (*tp))
1590 lineno = STMT_LINENO (*tp);
1591 #endif /* not INLINER_FOR_JAVA */
1593 /* Walk over all the sub-trees of this operand. */
1594 len = first_rtl_op (code);
1595 /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same.
1596 But, we only want to walk once. */
1597 if (code == TARGET_EXPR
1598 && TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1))
1600 /* Go through the subtrees. We need to do this in forward order so
1601 that the scope of a FOR_EXPR is handled properly. */
1602 for (i = 0; i < len; ++i)
1603 WALK_SUBTREE (TREE_OPERAND (*tp, i));
1605 #ifndef INLINER_FOR_JAVA
1606 /* For statements, we also walk the chain so that we cover the
1607 entire statement tree. */
1608 if (statement_code_p (code))
1610 if (code == DECL_STMT
1611 && DECL_STMT_DECL (*tp)
1612 && DECL_P (DECL_STMT_DECL (*tp)))
1614 /* Walk the DECL_INITIAL and DECL_SIZE. We don't want to walk
1615 into declarations that are just mentioned, rather than
1616 declared; they don't really belong to this part of the tree.
1617 And, we can see cycles: the initializer for a declaration can
1618 refer to the declaration itself. */
1619 WALK_SUBTREE (DECL_INITIAL (DECL_STMT_DECL (*tp)));
1620 WALK_SUBTREE (DECL_SIZE (DECL_STMT_DECL (*tp)));
1621 WALK_SUBTREE (DECL_SIZE_UNIT (DECL_STMT_DECL (*tp)));
1624 /* This can be tail-recursion optimized if we write it this way. */
1625 WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
1628 #endif /* not INLINER_FOR_JAVA */
1629 /* We didn't find what we were looking for. */
1632 else if (TREE_CODE_CLASS (code) == 'd')
1634 WALK_SUBTREE_TAIL (TREE_TYPE (*tp));
1636 else if (TREE_CODE_CLASS (code) == 't')
1638 WALK_SUBTREE (TYPE_SIZE (*tp));
1639 WALK_SUBTREE (TYPE_SIZE_UNIT (*tp));
1640 /* Also examine various special fields, below. */
1643 result = (*lang_hooks.tree_inlining.walk_subtrees) (tp, &walk_subtrees, func,
1645 if (result || ! walk_subtrees)
1648 /* Not one of the easy cases. We must explicitly go through the
1653 case IDENTIFIER_NODE:
1668 /* None of thse have subtrees other than those already walked
1673 case REFERENCE_TYPE:
1674 WALK_SUBTREE_TAIL (TREE_TYPE (*tp));
1678 WALK_SUBTREE (TREE_VALUE (*tp));
1679 WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
1684 int len = TREE_VEC_LENGTH (*tp);
1689 /* Walk all elements but the first. */
1691 WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
1693 /* Now walk the first one as a tail call. */
1694 WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0));
1698 WALK_SUBTREE (TREE_REALPART (*tp));
1699 WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp));
1702 WALK_SUBTREE_TAIL (CONSTRUCTOR_ELTS (*tp));
1705 WALK_SUBTREE (TYPE_METHOD_BASETYPE (*tp));
1709 WALK_SUBTREE (TREE_TYPE (*tp));
1711 tree arg = TYPE_ARG_TYPES (*tp);
1713 /* We never want to walk into default arguments. */
1714 for (; arg; arg = TREE_CHAIN (arg))
1715 WALK_SUBTREE (TREE_VALUE (arg));
1720 WALK_SUBTREE (TREE_TYPE (*tp));
1721 WALK_SUBTREE_TAIL (TYPE_DOMAIN (*tp));
1724 WALK_SUBTREE (TYPE_MIN_VALUE (*tp));
1725 WALK_SUBTREE_TAIL (TYPE_MAX_VALUE (*tp));
1728 WALK_SUBTREE (TREE_TYPE (*tp));
1729 WALK_SUBTREE_TAIL (TYPE_OFFSET_BASETYPE (*tp));
1731 #ifdef INLINER_FOR_JAVA
1732 case EXIT_BLOCK_EXPR:
1733 WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 1));
1736 WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 0));
1737 #endif /* INLINER_FOR_JAVA */
1743 /* We didn't find what we were looking for. */
1747 #undef WALK_SUBTREE_TAIL
1750 /* Like walk_tree, but does not walk duplicate nodes more than
1754 walk_tree_without_duplicates (tp, func, data)
1762 htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
1763 result = walk_tree (tp, func, data, htab);
1768 /* Passed to walk_tree. Copies the node pointed to, if appropriate. */
1771 copy_tree_r (tp, walk_subtrees, data)
1774 void *data ATTRIBUTE_UNUSED;
1776 enum tree_code code = TREE_CODE (*tp);
1778 /* We make copies of most nodes. */
1779 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
1780 || TREE_CODE_CLASS (code) == 'r'
1781 || TREE_CODE_CLASS (code) == 'c'
1782 || TREE_CODE_CLASS (code) == 's'
1783 || code == TREE_LIST
1785 || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp))
1787 /* Because the chain gets clobbered when we make a copy, we save it
1789 tree chain = TREE_CHAIN (*tp);
1791 /* Copy the node. */
1792 *tp = copy_node (*tp);
1794 /* Now, restore the chain, if appropriate. That will cause
1795 walk_tree to walk into the chain as well. */
1796 if (code == PARM_DECL || code == TREE_LIST
1797 #ifndef INLINER_FOR_JAVA
1798 || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp)
1799 || statement_code_p (code))
1800 TREE_CHAIN (*tp) = chain;
1802 /* For now, we don't update BLOCKs when we make copies. So, we
1803 have to nullify all scope-statements. */
1804 if (TREE_CODE (*tp) == SCOPE_STMT)
1805 SCOPE_STMT_BLOCK (*tp) = NULL_TREE;
1806 #else /* INLINER_FOR_JAVA */
1807 || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp))
1808 TREE_CHAIN (*tp) = chain;
1809 #endif /* INLINER_FOR_JAVA */
1811 else if (TREE_CODE_CLASS (code) == 't' && !variably_modified_type_p (*tp))
1812 /* Types only need to be copied if they are variably modified. */
1818 /* The SAVE_EXPR pointed to by TP is being copied. If ST contains
1819 information indicating to what new SAVE_EXPR this one should be
1820 mapped, use that one. Otherwise, create a new node and enter it in
1821 ST. FN is the function into which the copy will be placed. */
1824 remap_save_expr (tp, st_, fn, walk_subtrees)
1830 splay_tree st = (splay_tree) st_;
1833 /* See if we already encountered this SAVE_EXPR. */
1834 n = splay_tree_lookup (st, (splay_tree_key) *tp);
1836 /* If we didn't already remap this SAVE_EXPR, do so now. */
1839 tree t = copy_node (*tp);
1841 /* The SAVE_EXPR is now part of the function into which we
1842 are inlining this body. */
1843 SAVE_EXPR_CONTEXT (t) = fn;
1844 /* And we haven't evaluated it yet. */
1845 SAVE_EXPR_RTL (t) = NULL_RTX;
1846 /* Remember this SAVE_EXPR. */
1847 n = splay_tree_insert (st,
1848 (splay_tree_key) *tp,
1849 (splay_tree_value) t);
1850 /* Make sure we don't remap an already-remapped SAVE_EXPR. */
1851 splay_tree_insert (st, (splay_tree_key) t,
1852 (splay_tree_value) error_mark_node);
1855 /* We've already walked into this SAVE_EXPR, so we needn't do it
1859 /* Replace this SAVE_EXPR with the copy. */
1860 *tp = (tree) n->value;
1863 #ifdef INLINER_FOR_JAVA
1864 /* Add STMT to EXISTING if possible, otherwise create a new
1865 COMPOUND_EXPR and add STMT to it. */
1868 add_stmt_to_compound (existing, type, stmt)
1869 tree existing, type, stmt;
1874 return build (COMPOUND_EXPR, type, existing, stmt);
1879 #endif /* INLINER_FOR_JAVA */