1 /* Callgraph based intraprocedural optimizations.
2 Copyright (C) 2003 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
24 #include "coretypes.h"
27 #include "tree-inline.h"
28 #include "langhooks.h"
36 #include "diagnostic.h"
42 #define INSNS_PER_CALL 10
44 static void cgraph_expand_functions (void);
45 static void cgraph_mark_functions_to_output (void);
46 static void cgraph_expand_function (struct cgraph_node
*);
47 static tree
record_call_1 (tree
*, int *, void *);
48 static void cgraph_mark_local_functions (void);
49 static void cgraph_optimize_function (struct cgraph_node
*);
50 static bool cgraph_default_inline_p (struct cgraph_node
*n
);
51 static void cgraph_analyze_function (struct cgraph_node
*node
);
53 /* Statistics we collect about inlining algorithm. */
54 static int ncalls_inlined
;
55 static int nfunctions_inlined
;
56 static int initial_insns
;
57 static int overall_insns
;
59 /* Records tree nodes seen in cgraph_create_edges. Simply using
60 walk_tree_without_duplicates doesn't guarantee each node is visited
61 once because it gets a new htab upon each recursive call from
63 static htab_t visited_nodes
;
65 /* Determine if function DECL is needed. That is, visible to something
66 either outside this translation unit, something magic in the system
67 configury, or (if not doing unit-at-a-time) to something we havn't
71 decide_is_function_needed (struct cgraph_node
*node
, tree decl
)
73 /* If we decided it was needed before, but at the time we didn't have
74 the body of the function available, then it's still needed. We have
75 to go back and re-check its dependencies now. */
79 /* Externally visible functions must be output. The exception is
80 COMDAT functions that must be output only when they are needed. */
81 if (TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
) && !DECL_EXTERNAL (decl
))
84 /* Constructors and destructors are reachable from the runtime by
86 if (DECL_STATIC_CONSTRUCTOR (decl
) || DECL_STATIC_DESTRUCTOR (decl
))
89 /* If the user told us it is used, then it must be so. */
90 if (lookup_attribute ("used", DECL_ATTRIBUTES (decl
)))
93 /* ??? If the assembler name is set by hand, it is possible to assemble
94 the name later after finalizing the function and the fact is noticed
95 in assemble_name then. This is arguably a bug. */
96 if (DECL_ASSEMBLER_NAME_SET_P (decl
)
97 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
)))
100 if (flag_unit_at_a_time
)
103 /* If not doing unit at a time, then we'll only defer this function
104 if its marked for inlining. Otherwise we want to emit it now. */
106 /* "extern inline" functions are never output locally. */
107 if (DECL_EXTERNAL (decl
))
109 /* We want to emit COMDAT functions only when they turns out to be neccesary. */
110 if (DECL_COMDAT (decl
))
112 if (!DECL_INLINE (decl
)
113 || (!node
->local
.disregard_inline_limits
114 /* When declared inline, defer even the uninlinable functions.
115 This allows them to be elliminated when unused. */
116 && !DECL_DECLARED_INLINE_P (decl
)
117 && (node
->local
.inlinable
|| !cgraph_default_inline_p (node
))))
123 /* When not doing unit-at-a-time, output all functions enqueued.
124 Return true when such a functions were found. */
126 cgraph_assemble_pending_functions (void)
130 if (flag_unit_at_a_time
)
133 while (cgraph_nodes_queue
)
135 struct cgraph_node
*n
= cgraph_nodes_queue
;
137 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
138 if (!n
->origin
&& !DECL_EXTERNAL (n
->decl
))
139 cgraph_expand_function (n
);
145 /* Analyze function once it is parsed. Set up the local information
146 available - create cgraph edges for function calls via BODY. */
149 cgraph_finalize_function (tree decl
)
151 struct cgraph_node
*node
= cgraph_node (decl
);
153 if (node
->local
.finalized
)
155 /* As an GCC extension we allow redefinition of the function. The
156 semantics when both copies of bodies differ is not well defined. We
157 replace the old body with new body so in unit at a time mode we always
158 use new body, while in normal mode we may end up with old body inlined
159 into some functions and new body expanded and inlined in others.
161 ??? It may make more sense to use one body for inlining and other body
162 for expanding the function but this is dificult to do. */
163 /* Reset our datastructures so we can analyze the function body
165 memset (&node
->local
, 0, sizeof (node
->local
));
166 memset (&node
->global
, 0, sizeof (node
->global
));
167 memset (&node
->rtl
, 0, sizeof (node
->rtl
));
168 node
->lowered
= false;
171 while (node
->callees
)
172 cgraph_remove_call (node
->decl
, node
->callees
->callee
->decl
);
173 /* We may need to re-queue the node for assembling in case
174 we already proceeded it and ignored as not needed. */
175 if (node
->reachable
&& !flag_unit_at_a_time
)
177 struct cgraph_node
*n
;
179 for (n
= cgraph_nodes_queue
; n
; n
= n
->next_needed
)
186 notice_global_symbol (decl
);
188 node
->local
.finalized
= true;
190 /* If not unit at a time, then we need to create the call graph
191 now, so that called functions can be queued and emitted now. */
192 if (!flag_unit_at_a_time
)
193 cgraph_analyze_function (node
);
195 if (decide_is_function_needed (node
, decl
))
196 cgraph_mark_needed_node (node
);
198 /* If not unit at a time, go ahead and emit everything we've
199 found to be reachable at this time. Do this only at top-level. */
201 cgraph_assemble_pending_functions ();
203 /* If we've not yet emitted decl, tell the debug info about it. */
204 if (flag_unit_at_a_time
|| !node
->reachable
)
205 (*debug_hooks
->deferred_inline_function
) (decl
);
208 /* Walk tree and record all calls. Called via walk_tree. */
210 record_call_1 (tree
*tp
, int *walk_subtrees
, void *data
)
212 if (TREE_CODE (*tp
) == VAR_DECL
&& TREE_STATIC (*tp
))
213 cgraph_varpool_mark_needed_node (cgraph_varpool_node (*tp
));
214 /* Record dereferences to the functions. This makes the functions
215 reachable unconditionally. */
216 else if (TREE_CODE (*tp
) == ADDR_EXPR
&& flag_unit_at_a_time
)
218 tree decl
= TREE_OPERAND (*tp
, 0);
219 if (TREE_CODE (decl
) == FUNCTION_DECL
)
220 cgraph_mark_needed_node (cgraph_node (decl
));
222 else if (TREE_CODE (*tp
) == CALL_EXPR
)
224 tree decl
= get_callee_fndecl (*tp
);
225 if (decl
&& TREE_CODE (decl
) == FUNCTION_DECL
)
227 if (DECL_BUILT_IN (decl
))
229 cgraph_record_call (data
, decl
);
231 /* When we see a function call, we don't want to look at the
232 function reference in the ADDR_EXPR that is hanging from
233 the CALL_EXPR we're examining here, because we would
234 conclude incorrectly that the function's address could be
235 taken by something that is not a function call. So only
236 walk the function parameter list, skip the other subtrees. */
238 walk_tree (&TREE_OPERAND (*tp
, 1), record_call_1
, data
,
243 /* Save some cycles by not walking types and declaration as we won't find anything
244 usefull there anyway. */
245 if (DECL_P (*tp
) || TYPE_P (*tp
))
250 /* Create cgraph edges for function calls inside BODY from DECL. */
253 cgraph_create_edges (tree decl
, tree body
)
255 /* The nodes we're interested in are never shared, so walk
256 the tree ignoring duplicates. */
257 visited_nodes
= htab_create (37, htab_hash_pointer
,
258 htab_eq_pointer
, NULL
);
259 walk_tree (&body
, record_call_1
, decl
, visited_nodes
);
260 htab_delete (visited_nodes
);
261 visited_nodes
= NULL
;
264 /* Analyze the function scheduled to be output. */
266 cgraph_analyze_function (struct cgraph_node
*node
)
268 tree decl
= node
->decl
;
270 if (lang_hooks
.callgraph
.lower_function
)
271 (*lang_hooks
.callgraph
.lower_function
) (decl
);
273 current_function_decl
= node
->decl
;
275 /* First kill forward declaration so reverse inlining works properly. */
276 cgraph_create_edges (decl
, DECL_SAVED_TREE (decl
));
278 node
->local
.inlinable
= tree_inlinable_function_p (decl
);
279 if (!DECL_ESTIMATED_INSNS (decl
))
280 DECL_ESTIMATED_INSNS (decl
)
281 = (*lang_hooks
.tree_inlining
.estimate_num_insns
) (decl
);
282 node
->local
.self_insns
= DECL_ESTIMATED_INSNS (decl
);
283 if (node
->local
.inlinable
)
284 node
->local
.disregard_inline_limits
285 = (*lang_hooks
.tree_inlining
.disregard_inline_limits
) (decl
);
287 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
288 node
->global
.insns
= node
->local
.self_insns
;
289 if (!DECL_EXTERNAL (node
->decl
))
291 node
->global
.cloned_times
= 1;
292 node
->global
.will_be_output
= true;
295 node
->lowered
= true;
296 current_function_decl
= NULL
;
299 /* Analyze the whole compilation unit once it is parsed completely. */
302 cgraph_finalize_compilation_unit (void)
304 struct cgraph_node
*node
;
306 if (!flag_unit_at_a_time
)
308 cgraph_assemble_pending_functions ();
312 cgraph_varpool_assemble_pending_decls ();
314 fprintf (stderr
, "\nAnalyzing compilation unit\n");
316 timevar_push (TV_CGRAPH
);
317 if (cgraph_dump_file
)
319 fprintf (cgraph_dump_file
, "\nInitial entry points:");
320 for (node
= cgraph_nodes
; node
; node
= node
->next
)
321 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
322 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
323 fprintf (cgraph_dump_file
, "\n");
326 /* Propagate reachability flag and lower representation of all reachable
327 functions. In the future, lowering will introduce new functions and
328 new entry points on the way (by template instantiation and virtual
329 method table generation for instance). */
330 while (cgraph_nodes_queue
)
332 struct cgraph_edge
*edge
;
333 tree decl
= cgraph_nodes_queue
->decl
;
335 node
= cgraph_nodes_queue
;
336 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
338 /* ??? It is possible to create extern inline function and later using
339 weak alas attribute to kill it's body. See
340 gcc.c-torture/compile/20011119-1.c */
341 if (!DECL_SAVED_TREE (decl
))
344 if (node
->lowered
|| !node
->reachable
|| !DECL_SAVED_TREE (decl
))
347 cgraph_analyze_function (node
);
349 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
350 if (!edge
->callee
->reachable
)
351 cgraph_mark_reachable_node (edge
->callee
);
353 cgraph_varpool_assemble_pending_decls ();
356 /* Collect entry points to the unit. */
358 if (cgraph_dump_file
)
360 fprintf (cgraph_dump_file
, "\nUnit entry points:");
361 for (node
= cgraph_nodes
; node
; node
= node
->next
)
362 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
363 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
364 fprintf (cgraph_dump_file
, "\n");
365 dump_cgraph (cgraph_dump_file
);
368 if (cgraph_dump_file
)
369 fprintf (cgraph_dump_file
, "\nReclaiming functions:");
371 for (node
= cgraph_nodes
; node
; node
= node
->next
)
373 tree decl
= node
->decl
;
375 if (!node
->reachable
&& DECL_SAVED_TREE (decl
))
377 cgraph_remove_node (node
);
378 if (cgraph_dump_file
)
379 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
382 if (cgraph_dump_file
)
383 fprintf (cgraph_dump_file
, "\n");
385 timevar_pop (TV_CGRAPH
);
388 /* Figure out what functions we want to assemble. */
391 cgraph_mark_functions_to_output (void)
393 struct cgraph_node
*node
;
395 for (node
= cgraph_nodes
; node
; node
= node
->next
)
397 tree decl
= node
->decl
;
398 struct cgraph_edge
*e
;
402 for (e
= node
->callers
; e
; e
= e
->next_caller
)
406 /* We need to output all local functions that are used and not
407 always inlined, as well as those that are reachable from
408 outside the current compilation unit. */
409 if (DECL_SAVED_TREE (decl
)
411 || (e
&& node
->reachable
))
412 && !TREE_ASM_WRITTEN (decl
) && !node
->origin
413 && !DECL_EXTERNAL (decl
))
418 /* Optimize the function before expansion. */
421 cgraph_optimize_function (struct cgraph_node
*node
)
423 tree decl
= node
->decl
;
425 timevar_push (TV_INTEGRATION
);
426 /* optimize_inline_calls avoids inlining of current_function_decl. */
427 current_function_decl
= decl
;
428 if (flag_inline_trees
)
429 optimize_inline_calls (decl
);
432 for (node
= node
->nested
; node
; node
= node
->next_nested
)
433 cgraph_optimize_function (node
);
435 timevar_pop (TV_INTEGRATION
);
438 /* Expand function specified by NODE. */
441 cgraph_expand_function (struct cgraph_node
*node
)
443 tree decl
= node
->decl
;
444 struct cgraph_edge
*e
;
446 announce_function (decl
);
448 cgraph_optimize_function (node
);
450 /* Generate RTL for the body of DECL. Nested functions are expanded
451 via lang_expand_decl_stmt. */
452 (*lang_hooks
.callgraph
.expand_function
) (decl
);
454 if (!flag_unit_at_a_time
)
456 if (!node
->local
.inlinable
457 || (!node
->local
.disregard_inline_limits
458 && !cgraph_default_inline_p (node
)))
459 DECL_SAVED_TREE (node
->decl
) = NULL
;
463 for (e
= node
->callers
; e
; e
= e
->next_caller
)
467 DECL_SAVED_TREE (decl
) = NULL
;
469 current_function_decl
= NULL
;
472 /* Fill array order with all nodes with output flag set in the reverse
473 topological order. */
475 cgraph_postorder (struct cgraph_node
**order
)
477 struct cgraph_node
*node
, *node2
;
480 struct cgraph_edge
*edge
, last
;
482 struct cgraph_node
**stack
=
483 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
485 /* We have to deal with cycles nicely, so use a depth first traversal
486 output algorithm. Ignore the fact that some functions won't need
487 to be output and put them into order as well, so we get dependencies
488 right through intline functions. */
489 for (node
= cgraph_nodes
; node
; node
= node
->next
)
491 for (node
= cgraph_nodes
; node
; node
= node
->next
)
498 node
->aux
= node
->callers
;
501 while (node2
->aux
!= &last
)
504 if (edge
->next_caller
)
505 node2
->aux
= edge
->next_caller
;
508 if (!edge
->caller
->aux
)
510 if (!edge
->caller
->callers
)
511 edge
->caller
->aux
= &last
;
513 edge
->caller
->aux
= edge
->caller
->callers
;
514 stack
[stack_size
++] = node2
;
515 node2
= edge
->caller
;
519 if (node2
->aux
== &last
)
521 order
[order_pos
++] = node2
;
523 node2
= stack
[--stack_size
];
533 #define INLINED_TIMES(node) ((size_t)(node)->aux)
534 #define SET_INLINED_TIMES(node,times) ((node)->aux = (void *)(times))
536 /* Return list of nodes we decided to inline NODE into, set their output
537 flag and compute INLINED_TIMES.
539 We do simple backtracing to get INLINED_TIMES right. This should not be
540 expensive as we limit the amount of inlining. Alternatively we may first
541 discover set of nodes, topologically sort these and propagate
545 cgraph_inlined_into (struct cgraph_node
*node
, struct cgraph_node
**array
)
548 struct cgraph_edge
**stack
;
549 struct cgraph_edge
*e
, *e1
;
553 /* Fast path: since we traverse in mostly topological order, we will likely
555 for (e
= node
->callers
; e
; e
= e
->next_caller
)
562 /* Allocate stack for back-tracking up callgraph. */
563 stack
= xmalloc ((cgraph_n_nodes
+ 1) * sizeof (struct cgraph_edge
));
566 /* Push the first edge on to the stack. */
571 struct cgraph_node
*caller
;
573 /* Look at the edge on the top of the stack. */
577 /* Check if the caller destination has been visited yet. */
580 array
[nfound
++] = e
->caller
;
581 /* Mark that we have visited the destination. */
582 caller
->output
= true;
583 SET_INLINED_TIMES (caller
, 0);
585 SET_INLINED_TIMES (caller
, INLINED_TIMES (caller
) + 1);
587 for (e1
= caller
->callers
; e1
; e1
= e1
->next_caller
)
596 for (e1
= e
->next_caller
; e1
; e1
= e1
->next_caller
)
619 if (cgraph_dump_file
)
621 fprintf (cgraph_dump_file
, "Found inline predecesors of %s:",
622 cgraph_node_name (node
));
623 for (i
= 0; i
< nfound
; i
++)
625 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (array
[i
]));
626 if (INLINED_TIMES (array
[i
]) != 1)
627 fprintf (cgraph_dump_file
, " (%i times)",
628 (int)INLINED_TIMES (array
[i
]));
630 fprintf (cgraph_dump_file
, "\n");
636 /* Return list of nodes we decided to inline into NODE, set their output
637 flag and compute INLINED_TIMES.
639 This function is identical to cgraph_inlined_into with callers and callees
643 cgraph_inlined_callees (struct cgraph_node
*node
, struct cgraph_node
**array
)
646 struct cgraph_edge
**stack
;
647 struct cgraph_edge
*e
, *e1
;
651 /* Fast path: since we traverse in mostly topological order, we will likely
653 for (e
= node
->callees
; e
; e
= e
->next_callee
)
660 /* Allocate stack for back-tracking up callgraph. */
661 stack
= xmalloc ((cgraph_n_nodes
+ 1) * sizeof (struct cgraph_edge
));
664 /* Push the first edge on to the stack. */
669 struct cgraph_node
*callee
;
671 /* Look at the edge on the top of the stack. */
675 /* Check if the callee destination has been visited yet. */
678 array
[nfound
++] = e
->callee
;
679 /* Mark that we have visited the destination. */
680 callee
->output
= true;
681 SET_INLINED_TIMES (callee
, 0);
683 SET_INLINED_TIMES (callee
, INLINED_TIMES (callee
) + 1);
685 for (e1
= callee
->callees
; e1
; e1
= e1
->next_callee
)
694 for (e1
= e
->next_callee
; e1
; e1
= e1
->next_callee
)
716 if (cgraph_dump_file
)
718 fprintf (cgraph_dump_file
, "Found inline successors of %s:",
719 cgraph_node_name (node
));
720 for (i
= 0; i
< nfound
; i
++)
722 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (array
[i
]));
723 if (INLINED_TIMES (array
[i
]) != 1)
724 fprintf (cgraph_dump_file
, " (%i times)",
725 (int)INLINED_TIMES (array
[i
]));
727 fprintf (cgraph_dump_file
, "\n");
733 /* Estimate size of the function after inlining WHAT into TO. */
736 cgraph_estimate_size_after_inlining (int times
, struct cgraph_node
*to
,
737 struct cgraph_node
*what
)
739 return (what
->global
.insns
- INSNS_PER_CALL
) *times
+ to
->global
.insns
;
742 /* Estimate the growth caused by inlining NODE into all callees. */
745 cgraph_estimate_growth (struct cgraph_node
*node
)
749 int clones_added
= 0;
750 struct cgraph_edge
*e
;
752 for (e
= node
->callers
; e
; e
= e
->next_caller
)
755 growth
+= ((cgraph_estimate_size_after_inlining (1, e
->caller
, node
)
757 e
->caller
->global
.insns
) *e
->caller
->global
.cloned_times
);
758 calls_saved
+= e
->caller
->global
.cloned_times
;
759 clones_added
+= e
->caller
->global
.cloned_times
;
762 /* ??? Wrong for self recursive functions or cases where we decide to not
763 inline for different reasons, but it is not big deal as in that case
764 we will keep the body around, but we will also avoid some inlining. */
765 if (!node
->needed
&& !node
->origin
&& !DECL_EXTERNAL (node
->decl
))
766 growth
-= node
->global
.insns
, clones_added
--;
774 /* Update insn sizes after inlining WHAT into TO that is already inlined into
775 all nodes in INLINED array. */
778 cgraph_mark_inline (struct cgraph_node
*to
, struct cgraph_node
*what
,
779 struct cgraph_node
**inlined
, int ninlined
,
780 struct cgraph_node
**inlined_callees
,
781 int ninlined_callees
)
786 struct cgraph_edge
*e
;
790 for (e
= what
->callers
; e
; e
= e
->next_caller
)
796 e
->inline_call
= true;
798 clones
+= e
->caller
->global
.cloned_times
;
800 else if (!e
->inline_call
)
805 ncalls_inlined
+= times
;
807 new_insns
= cgraph_estimate_size_after_inlining (times
, to
, what
);
808 if (to
->global
.will_be_output
)
809 overall_insns
+= new_insns
- to
->global
.insns
;
810 to
->global
.insns
= new_insns
;
812 if (!called
&& !what
->needed
&& !what
->origin
813 && !DECL_EXTERNAL (what
->decl
))
815 if (!what
->global
.will_be_output
)
818 nfunctions_inlined
++;
819 what
->global
.will_be_output
= 0;
820 overall_insns
-= what
->global
.insns
;
822 what
->global
.cloned_times
+= clones
;
823 for (i
= 0; i
< ninlined
; i
++)
826 cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined
[i
]) *
827 times
, inlined
[i
], what
);
828 if (inlined
[i
]->global
.will_be_output
)
829 overall_insns
+= new_insns
- inlined
[i
]->global
.insns
;
830 inlined
[i
]->global
.insns
= new_insns
;
832 for (i
= 0; i
< ninlined_callees
; i
++)
834 inlined_callees
[i
]->global
.cloned_times
+=
835 INLINED_TIMES (inlined_callees
[i
]) * clones
;
839 /* Return false when inlining WHAT into TO is not good idea as it would cause
840 too large growth of function bodies. */
843 cgraph_check_inline_limits (struct cgraph_node
*to
, struct cgraph_node
*what
,
844 struct cgraph_node
**inlined
, int ninlined
)
848 struct cgraph_edge
*e
;
852 for (e
= to
->callees
; e
; e
= e
->next_callee
)
853 if (e
->callee
== what
)
856 /* When inlining large function body called once into small function,
857 take the inlined function as base for limiting the growth. */
858 if (to
->local
.self_insns
> what
->local
.self_insns
)
859 limit
= to
->local
.self_insns
;
861 limit
= what
->local
.self_insns
;
863 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
865 newsize
= cgraph_estimate_size_after_inlining (times
, to
, what
);
866 if (newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
869 for (i
= 0; i
< ninlined
; i
++)
872 cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined
[i
]) *
873 times
, inlined
[i
], what
);
874 if (newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
876 inlined
[i
]->local
.self_insns
*
877 (100 + PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
)) / 100)
883 /* Return true when function N is small enought to be inlined. */
886 cgraph_default_inline_p (struct cgraph_node
*n
)
888 if (!DECL_INLINE (n
->decl
) || !DECL_SAVED_TREE (n
->decl
))
890 if (DECL_DECLARED_INLINE_P (n
->decl
))
891 return n
->global
.insns
< MAX_INLINE_INSNS_SINGLE
;
893 return n
->global
.insns
< MAX_INLINE_INSNS_AUTO
;
896 /* We use greedy algorithm for inlining of small functions:
897 All inline candidates are put into prioritized heap based on estimated
898 growth of the overall number of instructions and then update the estimates.
900 INLINED and INLINED_CALEES are just pointers to arrays large enought
901 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
904 cgraph_decide_inlining_of_small_functions (struct cgraph_node
**inlined
,
905 struct cgraph_node
**inlined_callees
)
908 struct cgraph_node
*node
;
909 fibheap_t heap
= fibheap_new ();
910 struct fibnode
**heap_node
=
911 xcalloc (cgraph_max_uid
, sizeof (struct fibnode
*));
912 int ninlined
, ninlined_callees
;
913 int max_insns
= ((HOST_WIDEST_INT
) initial_insns
914 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
916 /* Put all inline candidates into the heap. */
918 for (node
= cgraph_nodes
; node
; node
= node
->next
)
920 struct cgraph_edge
*e
;
922 if (!node
->local
.inlinable
|| !node
->callers
923 || !cgraph_default_inline_p (node
))
926 /* Rule out always_inline functions we dealt with earlier. */
927 for (e
= node
->callers
; e
; e
= e
->next_caller
)
932 heap_node
[node
->uid
] =
933 fibheap_insert (heap
, cgraph_estimate_growth (node
), node
);
936 if (cgraph_dump_file
)
937 fprintf (cgraph_dump_file
, "\n\nDeciding on inlining: ");
938 while ((node
= fibheap_extract_min (heap
)) && overall_insns
<= max_insns
)
940 struct cgraph_edge
*e
;
941 int old_insns
= overall_insns
;
943 heap_node
[node
->uid
] = NULL
;
944 if (cgraph_dump_file
)
945 fprintf (cgraph_dump_file
, "Considering %s %i insns, growth %i.\n",
946 cgraph_node_name (node
), node
->global
.insns
,
947 cgraph_estimate_growth (node
));
948 if (!cgraph_default_inline_p (node
))
950 if (cgraph_dump_file
)
951 fprintf (cgraph_dump_file
, "Function too large.\n");
954 ninlined_callees
= cgraph_inlined_callees (node
, inlined_callees
);
955 for (e
= node
->callers
; e
; e
= e
->next_caller
)
956 if (!e
->inline_call
&& e
->caller
!= node
)
958 ninlined
= cgraph_inlined_into (e
->caller
, inlined
);
959 if (e
->callee
->output
960 || !cgraph_check_inline_limits (e
->caller
, node
, inlined
,
963 for (i
= 0; i
< ninlined
; i
++)
964 inlined
[i
]->output
= 0, node
->aux
= 0;
965 if (cgraph_dump_file
)
966 fprintf (cgraph_dump_file
, "Not inlining into %s\n",
967 cgraph_node_name (e
->caller
));
970 cgraph_mark_inline (e
->caller
, node
, inlined
, ninlined
,
971 inlined_callees
, ninlined_callees
);
972 if (heap_node
[e
->caller
->uid
])
973 fibheap_replace_key (heap
, heap_node
[e
->caller
->uid
],
974 cgraph_estimate_growth (e
->caller
));
976 /* Size of the functions we updated into has changed, so update
978 for (i
= 0; i
< ninlined
; i
++)
980 inlined
[i
]->output
= 0, node
->aux
= 0;
981 if (heap_node
[inlined
[i
]->uid
])
982 fibheap_replace_key (heap
, heap_node
[inlined
[i
]->uid
],
983 cgraph_estimate_growth (inlined
[i
]));
987 /* Similarly all functions called by function we just inlined
988 are now called more times; update keys. */
990 for (e
= node
->callees
; e
; e
= e
->next_callee
)
991 if (!e
->inline_call
&& heap_node
[e
->callee
->uid
])
992 fibheap_replace_key (heap
, heap_node
[e
->callee
->uid
],
993 cgraph_estimate_growth (e
->callee
));
995 for (i
= 0; i
< ninlined_callees
; i
++)
997 struct cgraph_edge
*e
;
999 for (e
= inlined_callees
[i
]->callees
; e
; e
= e
->next_callee
)
1000 if (!e
->inline_call
&& heap_node
[e
->callee
->uid
])
1001 fibheap_replace_key (heap
, heap_node
[e
->callee
->uid
],
1002 cgraph_estimate_growth (e
->callee
));
1004 inlined_callees
[i
]->output
= 0, node
->aux
= 0;
1006 if (cgraph_dump_file
)
1007 fprintf (cgraph_dump_file
,
1008 "Created %i clones, Num insns:%i (%+i), %.2f%%.\n\n",
1009 node
->global
.cloned_times
- 1,
1010 overall_insns
, overall_insns
- old_insns
,
1011 overall_insns
* 100.0 / initial_insns
);
1013 if (cgraph_dump_file
&& !fibheap_empty (heap
))
1014 fprintf (cgraph_dump_file
, "inline-unit-growth limit reached.\n");
1015 fibheap_delete (heap
);
1019 /* Decide on the inlining. We do so in the topological order to avoid
1020 expenses on updating datastructures. */
1023 cgraph_decide_inlining (void)
1025 struct cgraph_node
*node
;
1027 struct cgraph_node
**order
=
1028 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1029 struct cgraph_node
**inlined
=
1030 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1031 struct cgraph_node
**inlined_callees
=
1032 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1034 int ninlined_callees
;
1037 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1038 initial_insns
+= node
->local
.self_insns
;
1039 overall_insns
= initial_insns
;
1041 nnodes
= cgraph_postorder (order
);
1043 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1046 if (cgraph_dump_file
)
1047 fprintf (cgraph_dump_file
, "\n\nDeciding on always_inline functions:\n");
1049 /* In the first pass mark all always_inline edges. Do this with a priority
1050 so no our decisions makes this impossible. */
1051 for (i
= nnodes
- 1; i
>= 0; i
--)
1053 struct cgraph_edge
*e
;
1057 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1058 if (e
->callee
->local
.disregard_inline_limits
)
1062 if (cgraph_dump_file
)
1063 fprintf (cgraph_dump_file
,
1064 "Considering %s %i insns (always inline)\n",
1065 cgraph_node_name (node
), node
->global
.insns
);
1066 ninlined
= cgraph_inlined_into (order
[i
], inlined
);
1067 for (; e
; e
= e
->next_callee
)
1069 if (e
->inline_call
|| !e
->callee
->local
.disregard_inline_limits
)
1071 if (e
->callee
->output
|| e
->callee
== node
)
1074 cgraph_inlined_callees (e
->callee
, inlined_callees
);
1075 cgraph_mark_inline (node
, e
->callee
, inlined
, ninlined
,
1076 inlined_callees
, ninlined_callees
);
1077 for (y
= 0; y
< ninlined_callees
; y
++)
1078 inlined_callees
[y
]->output
= 0, node
->aux
= 0;
1079 if (cgraph_dump_file
)
1080 fprintf (cgraph_dump_file
, "Inlined %i times. Now %i insns\n\n",
1081 node
->global
.cloned_times
, overall_insns
);
1083 for (y
= 0; y
< ninlined
; y
++)
1084 inlined
[y
]->output
= 0, node
->aux
= 0;
1087 cgraph_decide_inlining_of_small_functions (inlined
, inlined_callees
);
1089 if (cgraph_dump_file
)
1090 fprintf (cgraph_dump_file
, "\n\nFunctions to inline once:\n");
1092 /* And finally decide what functions are called once. */
1094 for (i
= nnodes
- 1; i
>= 0; i
--)
1098 if (node
->callers
&& !node
->callers
->next_caller
&& !node
->needed
1099 && node
->local
.inlinable
&& !node
->callers
->inline_call
1100 && !DECL_EXTERNAL (node
->decl
) && !DECL_COMDAT (node
->decl
))
1103 struct cgraph_node
*node1
;
1105 /* Verify that we won't duplicate the caller. */
1106 for (node1
= node
->callers
->caller
;
1107 node1
->callers
&& node1
->callers
->inline_call
1108 && ok
; node1
= node1
->callers
->caller
)
1109 if (node1
->callers
->next_caller
|| node1
->needed
)
1113 if (cgraph_dump_file
)
1114 fprintf (cgraph_dump_file
,
1115 "Considering %s %i insns (called once)\n",
1116 cgraph_node_name (node
), node
->global
.insns
);
1117 ninlined
= cgraph_inlined_into (node
->callers
->caller
, inlined
);
1118 if (cgraph_check_inline_limits
1119 (node
->callers
->caller
, node
, inlined
, ninlined
))
1122 cgraph_inlined_callees (node
, inlined_callees
);
1123 cgraph_mark_inline (node
->callers
->caller
, node
, inlined
,
1124 ninlined
, inlined_callees
,
1126 for (y
= 0; y
< ninlined_callees
; y
++)
1127 inlined_callees
[y
]->output
= 0, node
->aux
= 0;
1128 if (cgraph_dump_file
)
1129 fprintf (cgraph_dump_file
, "Inlined. Now %i insns\n\n", overall_insns
);
1131 for (y
= 0; y
< ninlined
; y
++)
1132 inlined
[y
]->output
= 0, node
->aux
= 0;
1137 if (cgraph_dump_file
)
1138 fprintf (cgraph_dump_file
,
1139 "\nInlined %i calls, elliminated %i functions, %i insns turned to %i insns.\n",
1140 ncalls_inlined
, nfunctions_inlined
, initial_insns
,
1144 free (inlined_callees
);
1147 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
1150 cgraph_inline_p (tree caller_decl
, tree callee_decl
)
1152 struct cgraph_node
*caller
= cgraph_node (caller_decl
);
1153 struct cgraph_node
*callee
= cgraph_node (callee_decl
);
1154 struct cgraph_edge
*e
;
1156 for (e
= caller
->callees
; e
; e
= e
->next_callee
)
1157 if (e
->callee
== callee
)
1158 return e
->inline_call
;
1159 /* We do not record builtins in the callgraph. Perhaps it would make more
1160 sense to do so and then prune out those not overwritten by explicit
1164 /* Expand all functions that must be output.
1166 Attempt to topologically sort the nodes so function is output when
1167 all called functions are already assembled to allow data to be
1168 propagated across the callgraph. Use a stack to get smaller distance
1169 between a function and it's callees (later we may choose to use a more
1170 sophisticated algorithm for function reordering; we will likely want
1171 to use subsections to make the output functions appear in top-down
1175 cgraph_expand_functions (void)
1177 struct cgraph_node
*node
;
1178 struct cgraph_node
**order
=
1179 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1183 cgraph_mark_functions_to_output ();
1185 order_pos
= cgraph_postorder (order
);
1187 for (i
= order_pos
- 1; i
>= 0; i
--)
1192 if (!node
->reachable
)
1195 cgraph_expand_function (node
);
1201 /* Mark all local functions.
1203 A local function is one whose calls can occur only in the
1204 current compilation unit, so we change its calling convention.
1205 We simply mark all static functions whose address is not taken
1209 cgraph_mark_local_functions (void)
1211 struct cgraph_node
*node
;
1213 if (cgraph_dump_file
)
1214 fprintf (cgraph_dump_file
, "Marking local functions:");
1216 /* Figure out functions we want to assemble. */
1217 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1219 node
->local
.local
= (!node
->needed
1220 && DECL_SAVED_TREE (node
->decl
)
1221 && !TREE_PUBLIC (node
->decl
));
1222 if (cgraph_dump_file
&& node
->local
.local
)
1223 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
1225 if (cgraph_dump_file
)
1226 fprintf (cgraph_dump_file
, "\n");
1229 /* Perform simple optimizations based on callgraph. */
1232 cgraph_optimize (void)
1234 if (!flag_unit_at_a_time
)
1236 timevar_push (TV_CGRAPHOPT
);
1238 fprintf (stderr
, "Performing intraprocedural optimizations\n");
1239 if (cgraph_dump_file
)
1241 fprintf (cgraph_dump_file
, "Initial callgraph:");
1242 dump_cgraph (cgraph_dump_file
);
1244 cgraph_mark_local_functions ();
1246 cgraph_decide_inlining ();
1248 cgraph_global_info_ready
= true;
1249 if (cgraph_dump_file
)
1251 fprintf (cgraph_dump_file
, "Optimized callgraph:");
1252 dump_cgraph (cgraph_dump_file
);
1254 timevar_pop (TV_CGRAPHOPT
);
1256 fprintf (stderr
, "Assembling functions:");
1258 /* Output everything. */
1259 cgraph_expand_functions ();
1260 if (cgraph_dump_file
)
1262 fprintf (cgraph_dump_file
, "Final callgraph:");
1263 dump_cgraph (cgraph_dump_file
);