1 /* Perform optimizations on tree structure.
3 Copyright (C) 1998, 1999 Free Software Foundation, Inc.
4 Written by Mark Michell (mark@codesourcery.com).
6 This file is part of GNU CC.
8 GNU CC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GNU CC is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GNU CC; see the file COPYING. If not, write to the Free
20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
28 #include "insn-config.h"
29 #include "integrate.h"
34 o In order to make inlining-on-trees work, we pessimized
35 function-local static constants. In particular, they are now
36 always output, even when not addressed. Fix this by treating
37 function-local static constants just like global static
38 constants; the back-end already knows not to output them if they
41 o Provide heuristics to clamp inlining of recursive template
44 o It looks like the return label is not being placed in the optimal
45 place. Shouldn't it come before the returned value? */
47 /* Data required for function inlining. */
49 typedef struct inline_data
51 /* A stack of the functions we are inlining. For example, if we are
52 compiling `f', which calls `g', which calls `h', and we are
53 inlining the body of `h', the stack will contain, `h', followed
54 by `g', followed by `f'. */
56 /* The last SCOPE_STMT we have encountered. */
58 /* The label to jump to when a return statement is encountered. */
60 /* The map from local declarations in the inlined function to
61 equivalents in the function into which it is being inlined. */
63 /* Nonzero if we are currently within the cleanup for a
65 int in_target_cleanup_p
;
70 static tree initialize_inlined_parameters
PROTO((inline_data
*, tree
, tree
));
71 static tree declare_return_variable
PROTO((inline_data
*, tree
*));
72 static tree copy_body_r
PROTO((tree
*, int *, void *));
73 static tree copy_body
PROTO((inline_data
*));
74 static tree expand_call_inline
PROTO((tree
*, int *, void *));
75 static void expand_calls_inline
PROTO((tree
*, inline_data
*));
76 static int inlinable_function_p
PROTO((tree
, inline_data
*));
77 static tree remap_decl
PROTO((tree
, inline_data
*));
78 static void remap_block
PROTO((tree
, tree
, inline_data
*));
79 static void copy_scope_stmt
PROTO((tree
*, int *, inline_data
*));
80 static tree calls_setjmp_r
PROTO((tree
*, int *, void *));
82 /* Remap DECL during the copying of the BLOCK tree for the function.
83 DATA is really an `inline_data *'. */
93 /* We only remap local variables in the current function. */
94 fn
= VARRAY_TOP_TREE (id
->fns
);
95 if (!nonstatic_local_decl_p (decl
) || DECL_CONTEXT (decl
) != fn
)
98 /* See if we have remapped this declaration. */
99 n
= splay_tree_lookup (id
->decl_map
, (splay_tree_key
) decl
);
100 /* If we didn't already have an equivalent for this declaration,
106 /* Make a copy of the variable or label. */
107 t
= copy_decl_for_inlining (decl
, fn
,
108 VARRAY_TREE (id
->fns
, 0));
109 /* Remember it, so that if we encounter this local entity
110 again we can reuse this copy. */
111 n
= splay_tree_insert (id
->decl_map
,
112 (splay_tree_key
) decl
,
113 (splay_tree_value
) t
);
116 return (tree
) n
->value
;
119 /* Copy the SCOPE_STMT_BLOCK associated with SCOPE_STMT to contain
120 remapped versions of the variables therein. And hook the new block
121 into the block-tree. If non-NULL, the DECLS are declarations to
122 add to use instead of the BLOCK_VARS in the old block. */
125 remap_block (scope_stmt
, decls
, id
)
130 /* We cannot do this in the cleanup for a TARGET_EXPR since we do
131 not know whether or not expand_expr will actually write out the
132 code we put there. If it does not, then we'll have more BLOCKs
133 than block-notes, and things will go awry. At some point, we
134 should make the back-end handle BLOCK notes in a tidier way,
135 without requiring a strict correspondence to the block-tree; then
136 this check can go. */
137 if (id
->in_target_cleanup_p
)
139 SCOPE_STMT_BLOCK (scope_stmt
) = NULL_TREE
;
143 /* If this is the beginning of a scope, remap the associated BLOCK. */
144 if (SCOPE_BEGIN_P (scope_stmt
) && SCOPE_STMT_BLOCK (scope_stmt
))
150 /* Make the new block. */
151 old_block
= SCOPE_STMT_BLOCK (scope_stmt
);
152 new_block
= make_node (BLOCK
);
153 TREE_USED (new_block
) = TREE_USED (old_block
);
154 BLOCK_ABSTRACT_ORIGIN (new_block
) = old_block
;
155 SCOPE_STMT_BLOCK (scope_stmt
) = new_block
;
157 /* Remap its variables. */
158 for (old_var
= decls
? decls
: BLOCK_VARS (old_block
);
160 old_var
= TREE_CHAIN (old_var
))
164 /* Remap the variable. */
165 new_var
= remap_decl (old_var
, id
);
167 /* We didn't remap this variable, so we can't mess with
172 TREE_CHAIN (new_var
) = BLOCK_VARS (new_block
);
173 BLOCK_VARS (new_block
) = new_var
;
176 /* We put the BLOCK_VARS in reverse order; fix that now. */
177 BLOCK_VARS (new_block
) = nreverse (BLOCK_VARS (new_block
));
178 /* Graft the new block into the tree. */
179 insert_block_after_note (new_block
,
181 ? SCOPE_STMT_BLOCK (id
->scope_stmt
)
184 ? SCOPE_BEGIN_P (id
->scope_stmt
) : 1),
185 VARRAY_TREE (id
->fns
, 0));
186 /* Remember that this is now the last scope statement with
187 an associated block. */
188 id
->scope_stmt
= scope_stmt
;
189 /* Remember the remapped block. */
190 splay_tree_insert (id
->decl_map
,
191 (splay_tree_key
) old_block
,
192 (splay_tree_value
) new_block
);
194 /* If this is the end of a scope, set the SCOPE_STMT_BLOCK to be the
196 else if (SCOPE_END_P (scope_stmt
) && SCOPE_STMT_BLOCK (scope_stmt
))
200 /* Find this block in the table of remapped things. */
201 n
= splay_tree_lookup (id
->decl_map
,
202 (splay_tree_key
) SCOPE_STMT_BLOCK (scope_stmt
));
203 my_friendly_assert (n
!= NULL
, 19991203);
204 SCOPE_STMT_BLOCK (scope_stmt
) = (tree
) n
->value
;
206 /* Remember that this is now the last scope statement with an
208 id
->scope_stmt
= scope_stmt
;
212 /* Copy the SCOPE_STMT pointed to by TP. */
215 copy_scope_stmt (tp
, walk_subtrees
, id
)
222 /* Remember whether or not this statement was nullified. When
223 making a copy, copy_tree_r always sets SCOPE_NULLIFIED_P (and
224 doesn't copy the SCOPE_STMT_BLOCK) to free callers from having to
225 deal with copying BLOCKs if they do not wish to do so. */
226 block
= SCOPE_STMT_BLOCK (*tp
);
227 /* Copy (and replace) the statement. */
228 copy_tree_r (tp
, walk_subtrees
, NULL
);
229 /* Restore the SCOPE_STMT_BLOCK. */
230 SCOPE_STMT_BLOCK (*tp
) = block
;
232 /* Remap the associated block. */
233 remap_block (*tp
, NULL_TREE
, id
);
236 /* Called from copy_body via walk_tree. DATA is really an
240 copy_body_r (tp
, walk_subtrees
, data
)
249 id
= (inline_data
*) data
;
250 fn
= VARRAY_TOP_TREE (id
->fns
);
252 /* All automatic variables should have a DECL_CONTEXT indicating
253 what function they come from. */
254 if ((TREE_CODE (*tp
) == VAR_DECL
|| TREE_CODE (*tp
) == LABEL_DECL
)
255 && DECL_NAMESPACE_SCOPE_P (*tp
))
256 my_friendly_assert (DECL_EXTERNAL (*tp
) || TREE_STATIC (*tp
),
259 /* If this is a RETURN_STMT, change it into an EXPR_STMT and a
260 GOTO_STMT with the RET_LABEL as its target. */
261 if (TREE_CODE (*tp
) == RETURN_STMT
)
263 tree return_stmt
= *tp
;
266 /* Build the GOTO_STMT. */
267 goto_stmt
= build_min_nt (GOTO_STMT
, id
->ret_label
);
268 TREE_CHAIN (goto_stmt
) = TREE_CHAIN (return_stmt
);
270 /* If we're returning something, just turn that into an
271 assignment into the equivalent of the original
273 if (RETURN_EXPR (return_stmt
))
275 *tp
= build_min_nt (EXPR_STMT
,
276 RETURN_EXPR (return_stmt
));
277 /* And then jump to the end of the function. */
278 TREE_CHAIN (*tp
) = goto_stmt
;
280 /* If we're not returning anything just do the jump. */
284 /* Local variables and labels need to be replaced by equivalent
285 variables. We don't want to copy static variables; there's only
286 one of those, no matter how many times we inline the containing
288 else if (nonstatic_local_decl_p (*tp
) && DECL_CONTEXT (*tp
) == fn
)
292 /* Remap the declaration. */
293 new_decl
= remap_decl (*tp
, id
);
294 my_friendly_assert (new_decl
!= NULL_TREE
, 19991203);
295 /* Replace this variable with the copy. */
298 else if (TREE_CODE (*tp
) == SAVE_EXPR
)
299 remap_save_expr (tp
, id
->decl_map
, VARRAY_TREE (id
->fns
, 0));
300 else if (TREE_CODE (*tp
) == UNSAVE_EXPR
)
301 my_friendly_abort (19991113);
302 /* For a SCOPE_STMT, we must copy the associated block so that we
303 can write out debugging information for the inlined variables. */
304 else if (TREE_CODE (*tp
) == SCOPE_STMT
&& !id
->in_target_cleanup_p
)
305 copy_scope_stmt (tp
, walk_subtrees
, id
);
306 /* Otherwise, just copy the node. Note that copy_tree_r already
307 knows not to copy VAR_DECLs, etc., so this is safe. */
310 copy_tree_r (tp
, walk_subtrees
, NULL
);
312 /* The copied TARGET_EXPR has never been expanded, even if the
313 original node was expanded already. */
314 if (TREE_CODE (*tp
) == TARGET_EXPR
&& TREE_OPERAND (*tp
, 3))
315 TREE_OPERAND (*tp
, 1) = TREE_OPERAND (*tp
, 3);
316 /* Similarly, if we're copying a CALL_EXPR, the RTL for the
317 result is no longer valid. */
318 else if (TREE_CODE (*tp
) == CALL_EXPR
)
319 CALL_EXPR_RTL (*tp
) = NULL_RTX
;
322 /* Keep iterating. */
326 /* Make a copy of the body of FN so that it can be inserted inline in
335 body
= DECL_SAVED_TREE (VARRAY_TOP_TREE (id
->fns
));
336 walk_tree (&body
, copy_body_r
, id
);
341 /* Generate code to initialize the parameters of the function at the
342 top of the stack in ID from the ARGS (presented as a TREE_LIST). */
345 initialize_inlined_parameters (id
, args
, fn
)
355 /* Figure out what the parameters are. */
356 parms
= DECL_ARGUMENTS (fn
);
358 /* Start with no initializations whatsoever. */
359 init_stmts
= NULL_TREE
;
361 /* Loop through the parameter declarations, replacing each with an
362 equivalent VAR_DECL, appropriately initialized. */
363 for (p
= parms
, a
= args
; p
; a
= TREE_CHAIN (a
), p
= TREE_CHAIN (p
))
368 /* Make an equivalent VAR_DECL. */
369 var
= copy_decl_for_inlining (p
, fn
, VARRAY_TREE (id
->fns
, 0));
370 /* Register the VAR_DECL as the equivalent for the PARM_DECL;
371 that way, when the PARM_DECL is encountered, it will be
372 automatically replaced by the VAR_DECL. */
373 splay_tree_insert (id
->decl_map
,
375 (splay_tree_value
) var
);
376 /* Initialize this VAR_DECL from the equivalent argument. If
377 the argument is an object, created via a constructor or copy,
378 this will not result in an extra copy: the TARGET_EXPR
379 representing the argument will be bound to VAR, and the
380 object will be constructed in VAR. */
381 init_stmt
= build_min_nt (EXPR_STMT
,
382 build (INIT_EXPR
, TREE_TYPE (p
),
383 var
, TREE_VALUE (a
)));
384 /* Declare this new variable. Note that we do this *after* the
385 initialization because we are going to reverse all the
386 initialization statements below. */
387 TREE_CHAIN (init_stmt
) = build_min_nt (DECL_STMT
, var
);
388 /* Add this initialization to the list. */
389 TREE_CHAIN (TREE_CHAIN (init_stmt
)) = init_stmts
;
390 init_stmts
= init_stmt
;
393 /* The initialization statements have been built up in reverse
394 order. Straighten them out now. */
395 return nreverse (init_stmts
);
398 /* Declare a return variable to replace the RESULT_DECL for the
399 function we are calling. An appropriate DECL_STMT is returned.
400 The USE_STMT is filled in to contain a use of the declaration to
401 indicate the return value of the function. */
404 declare_return_variable (id
, use_stmt
)
405 struct inline_data
*id
;
408 tree fn
= VARRAY_TOP_TREE (id
->fns
);
409 tree result
= DECL_RESULT (fn
);
412 /* We don't need to do anything for functions that don't return
414 if (!result
|| same_type_p (TYPE_MAIN_VARIANT (TREE_TYPE (result
)),
417 *use_stmt
= NULL_TREE
;
421 /* Make an appropriate copy. */
422 var
= copy_decl_for_inlining (result
, fn
, VARRAY_TREE (id
->fns
, 0));
423 /* Register the VAR_DECL as the equivalent for the RESULT_DECL; that
424 way, when the RESULT_DECL is encountered, it will be
425 automatically replaced by the VAR_DECL. */
426 splay_tree_insert (id
->decl_map
,
427 (splay_tree_key
) result
,
428 (splay_tree_value
) var
);
430 /* Build the USE_STMT. */
431 *use_stmt
= build_min_nt (EXPR_STMT
, var
);
433 /* Build the declaration statement. */
434 return build_min_nt (DECL_STMT
, var
);
437 /* Returns non-zero if FN is a function that can be inlined. */
440 inlinable_function_p (fn
, id
)
446 /* If we've already decided this function shouldn't be inlined,
447 there's no need to check again. */
448 if (DECL_UNINLINABLE (fn
))
451 /* Assume it is not inlinable. */
454 /* If we're not inlining things, then nothing is inlinable. */
455 if (!flag_inline_trees
)
457 /* If the function was not declared `inline', then we don't inline
459 else if (!DECL_INLINE (fn
))
461 /* If we don't have the function body available, we can't inline
463 else if (!DECL_SAVED_TREE (fn
))
465 /* We can't inline varargs functions. */
466 else if (varargs_function_p (fn
))
468 /* All is well. We can inline this function. Traditionally, GCC
469 has refused to inline functions using setjmp or alloca, or
470 functions whose values are returned in a PARALLEL, and a few
471 other such obscure conditions. We are not equally constrained at
476 /* Squirrel away the result so that we don't have to check again. */
477 DECL_UNINLINABLE (fn
) = !inlinable
;
479 /* Don't do recursive inlining, either. We don't record this in
480 DECL_UNLINABLE; we may be able to inline this function later. */
485 for (i
= 0; i
< id
->fns
->elements_used
; ++i
)
486 if (VARRAY_TREE (id
->fns
, i
) == fn
)
490 /* We can inline a template instantiation only if its fully
493 && DECL_TEMPLATE_INFO (fn
)
494 && TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn
)))
496 fn
= instantiate_decl (fn
);
497 inlinable
= !TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn
));
500 /* Return the result. */
504 /* If *TP is CALL_EXPR, replace it with its inline expansion. */
507 expand_call_inline (tp
, walk_subtrees
, data
)
522 /* See what we've got. */
523 id
= (inline_data
*) data
;
526 /* Keep track of the last SCOPE_STMT we've seen. */
527 if (TREE_CODE (t
) == SCOPE_STMT
)
529 if (SCOPE_STMT_BLOCK (t
) && !id
->in_target_cleanup_p
)
534 /* Recurse, but letting recursive invocations know that we are
535 inside the body of a TARGET_EXPR. */
536 if (TREE_CODE (*tp
) == TARGET_EXPR
)
540 /* We're walking our own subtrees. */
543 /* Actually walk over them. This loop is the body of
544 walk_trees, omitting the case where the TARGET_EXPR
545 itself is handled. */
546 for (i
= first_rtl_op (TARGET_EXPR
) - 1; i
>= 0; --i
)
549 ++id
->in_target_cleanup_p
;
550 walk_tree (&TREE_OPERAND (*tp
, i
), expand_call_inline
, data
);
552 --id
->in_target_cleanup_p
;
558 /* From here on, we're only interested in CALL_EXPRs. */
559 if (TREE_CODE (t
) != CALL_EXPR
)
562 /* First, see if we can figure out what function is being called.
563 If we cannot, then there is no hope of inlining the function. */
564 fn
= get_callee_fndecl (t
);
568 /* Don't try to inline functions that are not well-suited to
570 if (!inlinable_function_p (fn
, id
))
573 /* Build a statement-expression containing code to initialize the
574 arguments, the actual inline expansion of the body, and a label
575 for the return statements within the function to jump to. The
576 type of the statement expression is the return type of the
578 expr
= build_min (STMT_EXPR
, TREE_TYPE (TREE_TYPE (fn
)), NULL_TREE
);
580 /* Local declarations will be replaced by their equivalents in this
583 id
->decl_map
= splay_tree_new (splay_tree_compare_pointers
,
586 /* Initialize the parameters. */
587 arg_inits
= initialize_inlined_parameters (id
, TREE_OPERAND (t
, 1), fn
);
588 /* Expand any inlined calls in the initializers. Do this before we
589 push FN on the stack of functions we are inlining; we want to
590 inline calls to FN that appear in the initializers for the
592 expand_calls_inline (&arg_inits
, id
);
593 /* And add them to the tree. */
594 STMT_EXPR_STMT (expr
) = chainon (STMT_EXPR_STMT (expr
), arg_inits
);
596 /* Record the function we are about to inline so that we can avoid
597 recursing into it. */
598 VARRAY_PUSH_TREE (id
->fns
, fn
);
600 /* Return statements in the function body will be replaced by jumps
602 id
->ret_label
= build_decl (LABEL_DECL
, NULL_TREE
, NULL_TREE
);
603 DECL_CONTEXT (id
->ret_label
) = VARRAY_TREE (id
->fns
, 0);
605 /* Create a block to put the parameters in. We have to do this
606 after the parameters have been remapped because remapping
607 parameters is different from remapping ordinary variables. */
608 scope_stmt
= build_min_nt (SCOPE_STMT
, DECL_INITIAL (fn
));
609 SCOPE_BEGIN_P (scope_stmt
) = 1;
610 SCOPE_NO_CLEANUPS_P (scope_stmt
) = 1;
611 remap_block (scope_stmt
, DECL_ARGUMENTS (fn
), id
);
612 TREE_CHAIN (scope_stmt
) = STMT_EXPR_STMT (expr
);
613 STMT_EXPR_STMT (expr
) = scope_stmt
;
614 id
->scope_stmt
= scope_stmt
;
616 /* Declare the return variable for the function. */
617 STMT_EXPR_STMT (expr
)
618 = chainon (STMT_EXPR_STMT (expr
),
619 declare_return_variable (id
, &use_stmt
));
621 /* After we've initialized the parameters, we insert the body of the
623 STMT_EXPR_STMT (expr
)
624 = chainon (STMT_EXPR_STMT (expr
), copy_body (id
));
626 /* Close the block for the parameters. */
627 scope_stmt
= build_min_nt (SCOPE_STMT
, DECL_INITIAL (fn
));
628 SCOPE_NO_CLEANUPS_P (scope_stmt
) = 1;
629 my_friendly_assert (DECL_INITIAL (fn
)
630 && TREE_CODE (DECL_INITIAL (fn
)) == BLOCK
,
632 remap_block (scope_stmt
, NULL_TREE
, id
);
633 STMT_EXPR_STMT (expr
)
634 = chainon (STMT_EXPR_STMT (expr
), scope_stmt
);
636 /* Finally, mention the returned value so that the value of the
637 statement-expression is the returned value of the function. */
638 STMT_EXPR_STMT (expr
) = chainon (STMT_EXPR_STMT (expr
), use_stmt
);
641 splay_tree_delete (id
->decl_map
);
644 /* After the body of the function comes the RET_LABEL. */
645 STMT_EXPR_STMT (expr
)
646 = chainon (STMT_EXPR_STMT (expr
),
647 build_min_nt (LABEL_STMT
, id
->ret_label
));
649 /* The new expression has side-effects if the old one did. */
650 TREE_SIDE_EFFECTS (expr
) = TREE_SIDE_EFFECTS (t
);
652 /* Replace the call by the inlined body. Wrap it in an
653 EXPR_WITH_FILE_LOCATION so that we'll get debugging line notes
654 pointing to the right place. */
655 chain
= TREE_CHAIN (*tp
);
656 *tp
= build_expr_wfl (expr
, DECL_SOURCE_FILE (fn
), DECL_SOURCE_LINE (fn
),
658 EXPR_WFL_EMIT_LINE_NOTE (*tp
) = 1;
659 TREE_CHAIN (*tp
) = chain
;
661 /* If the value of the new expression is ignored, that's OK. We
662 don't warn about this for CALL_EXPRs, so we shouldn't warn about
663 the equivalent inlined version either. */
666 /* Recurse into the body of the just inlined function. */
667 expand_calls_inline (tp
, id
);
668 VARRAY_POP (id
->fns
);
670 /* Don't walk into subtrees. We've already handled them above. */
673 /* Keep iterating. */
677 /* Walk over the entire tree *TP, replacing CALL_EXPRs with inline
678 expansions as appropriate. */
681 expand_calls_inline (tp
, id
)
685 /* Search through *TP, replacing all calls to inline functions by
686 appropriate equivalents. */
687 walk_tree (tp
, expand_call_inline
, id
);
690 /* Optimize the body of FN. */
693 optimize_function (fn
)
696 /* Expand calls to inline functions. */
697 if (flag_inline_trees
)
701 struct saved_scope
*s
;
704 memset (&id
, 0, sizeof (id
));
706 /* Don't allow recursion into FN. */
707 VARRAY_TREE_INIT (id
.fns
, 32, "fns");
708 VARRAY_PUSH_TREE (id
.fns
, fn
);
709 /* Or any functions that aren't finished yet. */
711 if (current_function_decl
)
713 VARRAY_PUSH_TREE (id
.fns
, current_function_decl
);
714 prev_fn
= current_function_decl
;
716 for (s
= scope_chain
; s
; s
= s
->prev
)
717 if (s
->function_decl
&& s
->function_decl
!= prev_fn
)
719 VARRAY_PUSH_TREE (id
.fns
, s
->function_decl
);
720 prev_fn
= s
->function_decl
;
722 /* Replace all calls to inline functions with the bodies of those
724 expand_calls_inline (&DECL_SAVED_TREE (fn
), &id
);
727 VARRAY_FREE (id
.fns
);
731 /* Called from calls_setjmp_p via walk_tree. */
734 calls_setjmp_r (tp
, walk_subtrees
, data
)
736 int *walk_subtrees ATTRIBUTE_UNUSED
;
737 void *data ATTRIBUTE_UNUSED
;
744 /* We're only interested in FUNCTION_DECLS. */
745 if (TREE_CODE (*tp
) != FUNCTION_DECL
)
748 special_function_p (*tp
, &setjmp_p
, &longjmp_p
, &malloc_p
, &alloca_p
);
750 return setjmp_p
? *tp
: NULL_TREE
;
753 /* Returns non-zero if FN calls `setjmp' or some other function that
754 can return more than once. This function is conservative; it may
755 occasionally return a non-zero value even when FN does not actually
762 return (walk_tree (&DECL_SAVED_TREE (fn
), calls_setjmp_r
, NULL
)