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 absolutely 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 /* DECL has been parsed. Take it, queue it, compile it at the whim of the
146 logic in effect. If NESTED is true, then our caller cannot stand to have
147 the garbage collector run at the moment. We would need to either create
148 a new GC context, or just not compile right now. */
151 cgraph_finalize_function (tree decl
, bool nested
)
153 struct cgraph_node
*node
= cgraph_node (decl
);
155 if (node
->local
.finalized
)
157 /* As an GCC extension we allow redefinition of the function. The
158 semantics when both copies of bodies differ is not well defined.
159 We replace the old body with new body so in unit at a time mode
160 we always use new body, while in normal mode we may end up with
161 old body inlined into some functions and new body expanded and
164 ??? It may make more sense to use one body for inlining and other
165 body for expanding the function but this is dificult to do. */
167 if (TREE_ASM_WRITTEN (decl
))
170 /* Reset our datastructures so we can analyze the function again. */
171 memset (&node
->local
, 0, sizeof (node
->local
));
172 memset (&node
->global
, 0, sizeof (node
->global
));
173 memset (&node
->rtl
, 0, sizeof (node
->rtl
));
174 node
->analyzed
= false;
175 while (node
->callees
)
176 cgraph_remove_call (node
->decl
, node
->callees
->callee
->decl
);
178 /* We may need to re-queue the node for assembling in case
179 we already proceeded it and ignored as not needed. */
180 if (node
->reachable
&& !flag_unit_at_a_time
)
182 struct cgraph_node
*n
;
184 for (n
= cgraph_nodes_queue
; n
; n
= n
->next_needed
)
192 notice_global_symbol (decl
);
194 node
->local
.finalized
= true;
196 /* If not unit at a time, then we need to create the call graph
197 now, so that called functions can be queued and emitted now. */
198 if (!flag_unit_at_a_time
)
199 cgraph_analyze_function (node
);
201 if (decide_is_function_needed (node
, decl
))
202 cgraph_mark_needed_node (node
);
204 /* If not unit at a time, go ahead and emit everything we've found
205 to be reachable at this time. */
207 cgraph_assemble_pending_functions ();
209 /* If we've not yet emitted decl, tell the debug info about it. */
210 if (!TREE_ASM_WRITTEN (decl
))
211 (*debug_hooks
->deferred_inline_function
) (decl
);
214 /* Walk tree and record all calls. Called via walk_tree. */
216 record_call_1 (tree
*tp
, int *walk_subtrees
, void *data
)
220 switch (TREE_CODE (t
))
223 /* ??? Really, we should mark this decl as *potentially* referenced
224 by this function and re-examine whether the decl is actually used
225 after rtl has been generated. */
227 cgraph_varpool_mark_needed_node (cgraph_varpool_node (t
));
231 if (flag_unit_at_a_time
)
233 /* Record dereferences to the functions. This makes the
234 functions reachable unconditionally. */
235 tree decl
= TREE_OPERAND (*tp
, 0);
236 if (TREE_CODE (decl
) == FUNCTION_DECL
)
237 cgraph_mark_needed_node (cgraph_node (decl
));
243 tree decl
= get_callee_fndecl (*tp
);
244 if (decl
&& TREE_CODE (decl
) == FUNCTION_DECL
)
246 if (DECL_BUILT_IN (decl
))
248 cgraph_record_call (data
, decl
);
250 /* When we see a function call, we don't want to look at the
251 function reference in the ADDR_EXPR that is hanging from
252 the CALL_EXPR we're examining here, because we would
253 conclude incorrectly that the function's address could be
254 taken by something that is not a function call. So only
255 walk the function parameter list, skip the other subtrees. */
257 walk_tree (&TREE_OPERAND (*tp
, 1), record_call_1
, data
,
265 /* Save some cycles by not walking types and declaration as we
266 won't find anything useful there anyway. */
267 if (DECL_P (*tp
) || TYPE_P (*tp
))
273 if ((unsigned int) TREE_CODE (t
) >= LAST_AND_UNUSED_TREE_CODE
)
274 return (*lang_hooks
.callgraph
.analyze_expr
) (tp
, walk_subtrees
, data
);
281 /* Create cgraph edges for function calls inside BODY from DECL. */
284 cgraph_create_edges (tree decl
, tree body
)
286 /* The nodes we're interested in are never shared, so walk
287 the tree ignoring duplicates. */
288 visited_nodes
= htab_create (37, htab_hash_pointer
,
289 htab_eq_pointer
, NULL
);
290 walk_tree (&body
, record_call_1
, decl
, visited_nodes
);
291 htab_delete (visited_nodes
);
292 visited_nodes
= NULL
;
295 /* Analyze the function scheduled to be output. */
297 cgraph_analyze_function (struct cgraph_node
*node
)
299 tree decl
= node
->decl
;
301 current_function_decl
= decl
;
303 /* First kill forward declaration so reverse inlining works properly. */
304 cgraph_create_edges (decl
, DECL_SAVED_TREE (decl
));
306 node
->local
.inlinable
= tree_inlinable_function_p (decl
);
307 if (!DECL_ESTIMATED_INSNS (decl
))
308 DECL_ESTIMATED_INSNS (decl
)
309 = (*lang_hooks
.tree_inlining
.estimate_num_insns
) (decl
);
310 node
->local
.self_insns
= DECL_ESTIMATED_INSNS (decl
);
311 if (node
->local
.inlinable
)
312 node
->local
.disregard_inline_limits
313 = (*lang_hooks
.tree_inlining
.disregard_inline_limits
) (decl
);
315 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
316 node
->global
.insns
= node
->local
.self_insns
;
317 if (!DECL_EXTERNAL (decl
))
319 node
->global
.cloned_times
= 1;
320 node
->global
.will_be_output
= true;
323 node
->analyzed
= true;
324 current_function_decl
= NULL
;
327 /* Analyze the whole compilation unit once it is parsed completely. */
330 cgraph_finalize_compilation_unit (void)
332 struct cgraph_node
*node
;
334 if (!flag_unit_at_a_time
)
336 cgraph_assemble_pending_functions ();
340 cgraph_varpool_assemble_pending_decls ();
342 fprintf (stderr
, "\nAnalyzing compilation unit\n");
344 timevar_push (TV_CGRAPH
);
345 if (cgraph_dump_file
)
347 fprintf (cgraph_dump_file
, "\nInitial entry points:");
348 for (node
= cgraph_nodes
; node
; node
= node
->next
)
349 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
350 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
351 fprintf (cgraph_dump_file
, "\n");
354 /* Propagate reachability flag and lower representation of all reachable
355 functions. In the future, lowering will introduce new functions and
356 new entry points on the way (by template instantiation and virtual
357 method table generation for instance). */
358 while (cgraph_nodes_queue
)
360 struct cgraph_edge
*edge
;
361 tree decl
= cgraph_nodes_queue
->decl
;
363 node
= cgraph_nodes_queue
;
364 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
366 /* ??? It is possible to create extern inline function and later using
367 weak alas attribute to kill it's body. See
368 gcc.c-torture/compile/20011119-1.c */
369 if (!DECL_SAVED_TREE (decl
))
372 if (node
->analyzed
|| !node
->reachable
|| !DECL_SAVED_TREE (decl
))
375 cgraph_analyze_function (node
);
377 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
378 if (!edge
->callee
->reachable
)
379 cgraph_mark_reachable_node (edge
->callee
);
381 cgraph_varpool_assemble_pending_decls ();
384 /* Collect entry points to the unit. */
386 if (cgraph_dump_file
)
388 fprintf (cgraph_dump_file
, "\nUnit entry points:");
389 for (node
= cgraph_nodes
; node
; node
= node
->next
)
390 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
391 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
392 fprintf (cgraph_dump_file
, "\n");
393 dump_cgraph (cgraph_dump_file
);
396 if (cgraph_dump_file
)
397 fprintf (cgraph_dump_file
, "\nReclaiming functions:");
399 for (node
= cgraph_nodes
; node
; node
= node
->next
)
401 tree decl
= node
->decl
;
403 if (!node
->reachable
&& DECL_SAVED_TREE (decl
))
405 cgraph_remove_node (node
);
406 if (cgraph_dump_file
)
407 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
410 if (cgraph_dump_file
)
411 fprintf (cgraph_dump_file
, "\n");
413 timevar_pop (TV_CGRAPH
);
416 /* Figure out what functions we want to assemble. */
419 cgraph_mark_functions_to_output (void)
421 struct cgraph_node
*node
;
423 for (node
= cgraph_nodes
; node
; node
= node
->next
)
425 tree decl
= node
->decl
;
426 struct cgraph_edge
*e
;
430 for (e
= node
->callers
; e
; e
= e
->next_caller
)
434 /* We need to output all local functions that are used and not
435 always inlined, as well as those that are reachable from
436 outside the current compilation unit. */
437 if (DECL_SAVED_TREE (decl
)
439 || (e
&& node
->reachable
))
440 && !TREE_ASM_WRITTEN (decl
) && !node
->origin
441 && !DECL_EXTERNAL (decl
))
446 /* Optimize the function before expansion. */
449 cgraph_optimize_function (struct cgraph_node
*node
)
451 tree decl
= node
->decl
;
453 timevar_push (TV_INTEGRATION
);
454 /* optimize_inline_calls avoids inlining of current_function_decl. */
455 current_function_decl
= decl
;
456 if (flag_inline_trees
)
457 optimize_inline_calls (decl
);
460 for (node
= node
->nested
; node
; node
= node
->next_nested
)
461 cgraph_optimize_function (node
);
463 timevar_pop (TV_INTEGRATION
);
466 /* Expand function specified by NODE. */
469 cgraph_expand_function (struct cgraph_node
*node
)
471 tree decl
= node
->decl
;
472 struct cgraph_edge
*e
;
474 if (flag_unit_at_a_time
)
475 announce_function (decl
);
477 cgraph_optimize_function (node
);
479 /* Generate RTL for the body of DECL. Nested functions are expanded
480 via lang_expand_decl_stmt. */
481 (*lang_hooks
.callgraph
.expand_function
) (decl
);
483 if (!flag_unit_at_a_time
)
485 if (!node
->local
.inlinable
486 || (!node
->local
.disregard_inline_limits
487 && !cgraph_default_inline_p (node
)))
488 DECL_SAVED_TREE (node
->decl
) = NULL
;
492 for (e
= node
->callers
; e
; e
= e
->next_caller
)
496 DECL_SAVED_TREE (decl
) = NULL
;
498 current_function_decl
= NULL
;
501 /* Fill array order with all nodes with output flag set in the reverse
502 topological order. */
504 cgraph_postorder (struct cgraph_node
**order
)
506 struct cgraph_node
*node
, *node2
;
509 struct cgraph_edge
*edge
, last
;
511 struct cgraph_node
**stack
=
512 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
514 /* We have to deal with cycles nicely, so use a depth first traversal
515 output algorithm. Ignore the fact that some functions won't need
516 to be output and put them into order as well, so we get dependencies
517 right through intline functions. */
518 for (node
= cgraph_nodes
; node
; node
= node
->next
)
520 for (node
= cgraph_nodes
; node
; node
= node
->next
)
527 node
->aux
= node
->callers
;
530 while (node2
->aux
!= &last
)
533 if (edge
->next_caller
)
534 node2
->aux
= edge
->next_caller
;
537 if (!edge
->caller
->aux
)
539 if (!edge
->caller
->callers
)
540 edge
->caller
->aux
= &last
;
542 edge
->caller
->aux
= edge
->caller
->callers
;
543 stack
[stack_size
++] = node2
;
544 node2
= edge
->caller
;
548 if (node2
->aux
== &last
)
550 order
[order_pos
++] = node2
;
552 node2
= stack
[--stack_size
];
562 #define INLINED_TIMES(node) ((size_t)(node)->aux)
563 #define SET_INLINED_TIMES(node,times) ((node)->aux = (void *)(times))
565 /* Return list of nodes we decided to inline NODE into, set their output
566 flag and compute INLINED_TIMES.
568 We do simple backtracing to get INLINED_TIMES right. This should not be
569 expensive as we limit the amount of inlining. Alternatively we may first
570 discover set of nodes, topologically sort these and propagate
574 cgraph_inlined_into (struct cgraph_node
*node
, struct cgraph_node
**array
)
577 struct cgraph_edge
**stack
;
578 struct cgraph_edge
*e
, *e1
;
582 /* Fast path: since we traverse in mostly topological order, we will likely
584 for (e
= node
->callers
; e
; e
= e
->next_caller
)
591 /* Allocate stack for back-tracking up callgraph. */
592 stack
= xmalloc ((cgraph_n_nodes
+ 1) * sizeof (struct cgraph_edge
));
595 /* Push the first edge on to the stack. */
600 struct cgraph_node
*caller
;
602 /* Look at the edge on the top of the stack. */
606 /* Check if the caller destination has been visited yet. */
609 array
[nfound
++] = e
->caller
;
610 /* Mark that we have visited the destination. */
611 caller
->output
= true;
612 SET_INLINED_TIMES (caller
, 0);
614 SET_INLINED_TIMES (caller
, INLINED_TIMES (caller
) + 1);
616 for (e1
= caller
->callers
; e1
; e1
= e1
->next_caller
)
625 for (e1
= e
->next_caller
; e1
; e1
= e1
->next_caller
)
648 if (cgraph_dump_file
)
650 fprintf (cgraph_dump_file
, "Found inline predecesors of %s:",
651 cgraph_node_name (node
));
652 for (i
= 0; i
< nfound
; i
++)
654 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (array
[i
]));
655 if (INLINED_TIMES (array
[i
]) != 1)
656 fprintf (cgraph_dump_file
, " (%i times)",
657 (int)INLINED_TIMES (array
[i
]));
659 fprintf (cgraph_dump_file
, "\n");
665 /* Return list of nodes we decided to inline into NODE, set their output
666 flag and compute INLINED_TIMES.
668 This function is identical to cgraph_inlined_into with callers and callees
672 cgraph_inlined_callees (struct cgraph_node
*node
, struct cgraph_node
**array
)
675 struct cgraph_edge
**stack
;
676 struct cgraph_edge
*e
, *e1
;
680 /* Fast path: since we traverse in mostly topological order, we will likely
682 for (e
= node
->callees
; e
; e
= e
->next_callee
)
689 /* Allocate stack for back-tracking up callgraph. */
690 stack
= xmalloc ((cgraph_n_nodes
+ 1) * sizeof (struct cgraph_edge
));
693 /* Push the first edge on to the stack. */
698 struct cgraph_node
*callee
;
700 /* Look at the edge on the top of the stack. */
704 /* Check if the callee destination has been visited yet. */
707 array
[nfound
++] = e
->callee
;
708 /* Mark that we have visited the destination. */
709 callee
->output
= true;
710 SET_INLINED_TIMES (callee
, 0);
712 SET_INLINED_TIMES (callee
, INLINED_TIMES (callee
) + 1);
714 for (e1
= callee
->callees
; e1
; e1
= e1
->next_callee
)
723 for (e1
= e
->next_callee
; e1
; e1
= e1
->next_callee
)
745 if (cgraph_dump_file
)
747 fprintf (cgraph_dump_file
, "Found inline successors of %s:",
748 cgraph_node_name (node
));
749 for (i
= 0; i
< nfound
; i
++)
751 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (array
[i
]));
752 if (INLINED_TIMES (array
[i
]) != 1)
753 fprintf (cgraph_dump_file
, " (%i times)",
754 (int)INLINED_TIMES (array
[i
]));
756 fprintf (cgraph_dump_file
, "\n");
762 /* Estimate size of the function after inlining WHAT into TO. */
765 cgraph_estimate_size_after_inlining (int times
, struct cgraph_node
*to
,
766 struct cgraph_node
*what
)
768 return (what
->global
.insns
- INSNS_PER_CALL
) *times
+ to
->global
.insns
;
771 /* Estimate the growth caused by inlining NODE into all callees. */
774 cgraph_estimate_growth (struct cgraph_node
*node
)
778 int clones_added
= 0;
779 struct cgraph_edge
*e
;
781 for (e
= node
->callers
; e
; e
= e
->next_caller
)
784 growth
+= ((cgraph_estimate_size_after_inlining (1, e
->caller
, node
)
786 e
->caller
->global
.insns
) *e
->caller
->global
.cloned_times
);
787 calls_saved
+= e
->caller
->global
.cloned_times
;
788 clones_added
+= e
->caller
->global
.cloned_times
;
791 /* ??? Wrong for self recursive functions or cases where we decide to not
792 inline for different reasons, but it is not big deal as in that case
793 we will keep the body around, but we will also avoid some inlining. */
794 if (!node
->needed
&& !node
->origin
&& !DECL_EXTERNAL (node
->decl
))
795 growth
-= node
->global
.insns
, clones_added
--;
803 /* Update insn sizes after inlining WHAT into TO that is already inlined into
804 all nodes in INLINED array. */
807 cgraph_mark_inline (struct cgraph_node
*to
, struct cgraph_node
*what
,
808 struct cgraph_node
**inlined
, int ninlined
,
809 struct cgraph_node
**inlined_callees
,
810 int ninlined_callees
)
815 struct cgraph_edge
*e
;
819 for (e
= what
->callers
; e
; e
= e
->next_caller
)
825 e
->inline_call
= true;
827 clones
+= e
->caller
->global
.cloned_times
;
829 else if (!e
->inline_call
)
834 ncalls_inlined
+= times
;
836 new_insns
= cgraph_estimate_size_after_inlining (times
, to
, what
);
837 if (to
->global
.will_be_output
)
838 overall_insns
+= new_insns
- to
->global
.insns
;
839 to
->global
.insns
= new_insns
;
841 if (!called
&& !what
->needed
&& !what
->origin
842 && !DECL_EXTERNAL (what
->decl
))
844 if (!what
->global
.will_be_output
)
847 nfunctions_inlined
++;
848 what
->global
.will_be_output
= 0;
849 overall_insns
-= what
->global
.insns
;
851 what
->global
.cloned_times
+= clones
;
852 for (i
= 0; i
< ninlined
; i
++)
855 cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined
[i
]) *
856 times
, inlined
[i
], what
);
857 if (inlined
[i
]->global
.will_be_output
)
858 overall_insns
+= new_insns
- inlined
[i
]->global
.insns
;
859 inlined
[i
]->global
.insns
= new_insns
;
861 for (i
= 0; i
< ninlined_callees
; i
++)
863 inlined_callees
[i
]->global
.cloned_times
+=
864 INLINED_TIMES (inlined_callees
[i
]) * clones
;
868 /* Return false when inlining WHAT into TO is not good idea as it would cause
869 too large growth of function bodies. */
872 cgraph_check_inline_limits (struct cgraph_node
*to
, struct cgraph_node
*what
,
873 struct cgraph_node
**inlined
, int ninlined
)
877 struct cgraph_edge
*e
;
881 for (e
= to
->callees
; e
; e
= e
->next_callee
)
882 if (e
->callee
== what
)
885 /* When inlining large function body called once into small function,
886 take the inlined function as base for limiting the growth. */
887 if (to
->local
.self_insns
> what
->local
.self_insns
)
888 limit
= to
->local
.self_insns
;
890 limit
= what
->local
.self_insns
;
892 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
894 newsize
= cgraph_estimate_size_after_inlining (times
, to
, what
);
895 if (newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
898 for (i
= 0; i
< ninlined
; i
++)
901 cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined
[i
]) *
902 times
, inlined
[i
], what
);
903 if (newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
905 inlined
[i
]->local
.self_insns
*
906 (100 + PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
)) / 100)
912 /* Return true when function N is small enought to be inlined. */
915 cgraph_default_inline_p (struct cgraph_node
*n
)
917 if (!DECL_INLINE (n
->decl
) || !DECL_SAVED_TREE (n
->decl
))
919 if (DECL_DECLARED_INLINE_P (n
->decl
))
920 return n
->global
.insns
< MAX_INLINE_INSNS_SINGLE
;
922 return n
->global
.insns
< MAX_INLINE_INSNS_AUTO
;
925 /* We use greedy algorithm for inlining of small functions:
926 All inline candidates are put into prioritized heap based on estimated
927 growth of the overall number of instructions and then update the estimates.
929 INLINED and INLINED_CALEES are just pointers to arrays large enought
930 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
933 cgraph_decide_inlining_of_small_functions (struct cgraph_node
**inlined
,
934 struct cgraph_node
**inlined_callees
)
937 struct cgraph_node
*node
;
938 fibheap_t heap
= fibheap_new ();
939 struct fibnode
**heap_node
=
940 xcalloc (cgraph_max_uid
, sizeof (struct fibnode
*));
941 int ninlined
, ninlined_callees
;
942 int max_insns
= ((HOST_WIDEST_INT
) initial_insns
943 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
945 /* Put all inline candidates into the heap. */
947 for (node
= cgraph_nodes
; node
; node
= node
->next
)
949 struct cgraph_edge
*e
;
951 if (!node
->local
.inlinable
|| !node
->callers
952 || !cgraph_default_inline_p (node
))
955 /* Rule out always_inline functions we dealt with earlier. */
956 for (e
= node
->callers
; e
; e
= e
->next_caller
)
961 heap_node
[node
->uid
] =
962 fibheap_insert (heap
, cgraph_estimate_growth (node
), node
);
965 if (cgraph_dump_file
)
966 fprintf (cgraph_dump_file
, "\n\nDeciding on inlining: ");
967 while ((node
= fibheap_extract_min (heap
)) && overall_insns
<= max_insns
)
969 struct cgraph_edge
*e
;
970 int old_insns
= overall_insns
;
972 heap_node
[node
->uid
] = NULL
;
973 if (cgraph_dump_file
)
974 fprintf (cgraph_dump_file
, "Considering %s %i insns, growth %i.\n",
975 cgraph_node_name (node
), node
->global
.insns
,
976 cgraph_estimate_growth (node
));
977 if (!cgraph_default_inline_p (node
))
979 if (cgraph_dump_file
)
980 fprintf (cgraph_dump_file
, "Function too large.\n");
983 ninlined_callees
= cgraph_inlined_callees (node
, inlined_callees
);
984 for (e
= node
->callers
; e
; e
= e
->next_caller
)
985 if (!e
->inline_call
&& e
->caller
!= node
)
987 ninlined
= cgraph_inlined_into (e
->caller
, inlined
);
988 if (e
->callee
->output
989 || !cgraph_check_inline_limits (e
->caller
, node
, inlined
,
992 for (i
= 0; i
< ninlined
; i
++)
993 inlined
[i
]->output
= 0, node
->aux
= 0;
994 if (cgraph_dump_file
)
995 fprintf (cgraph_dump_file
, "Not inlining into %s\n",
996 cgraph_node_name (e
->caller
));
999 cgraph_mark_inline (e
->caller
, node
, inlined
, ninlined
,
1000 inlined_callees
, ninlined_callees
);
1001 if (heap_node
[e
->caller
->uid
])
1002 fibheap_replace_key (heap
, heap_node
[e
->caller
->uid
],
1003 cgraph_estimate_growth (e
->caller
));
1005 /* Size of the functions we updated into has changed, so update
1007 for (i
= 0; i
< ninlined
; i
++)
1009 inlined
[i
]->output
= 0, node
->aux
= 0;
1010 if (heap_node
[inlined
[i
]->uid
])
1011 fibheap_replace_key (heap
, heap_node
[inlined
[i
]->uid
],
1012 cgraph_estimate_growth (inlined
[i
]));
1016 /* Similarly all functions called by function we just inlined
1017 are now called more times; update keys. */
1019 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1020 if (!e
->inline_call
&& heap_node
[e
->callee
->uid
])
1021 fibheap_replace_key (heap
, heap_node
[e
->callee
->uid
],
1022 cgraph_estimate_growth (e
->callee
));
1024 for (i
= 0; i
< ninlined_callees
; i
++)
1026 struct cgraph_edge
*e
;
1028 for (e
= inlined_callees
[i
]->callees
; e
; e
= e
->next_callee
)
1029 if (!e
->inline_call
&& heap_node
[e
->callee
->uid
])
1030 fibheap_replace_key (heap
, heap_node
[e
->callee
->uid
],
1031 cgraph_estimate_growth (e
->callee
));
1033 inlined_callees
[i
]->output
= 0, node
->aux
= 0;
1035 if (cgraph_dump_file
)
1036 fprintf (cgraph_dump_file
,
1037 "Created %i clones, Num insns:%i (%+i), %.2f%%.\n\n",
1038 node
->global
.cloned_times
- 1,
1039 overall_insns
, overall_insns
- old_insns
,
1040 overall_insns
* 100.0 / initial_insns
);
1042 if (cgraph_dump_file
&& !fibheap_empty (heap
))
1043 fprintf (cgraph_dump_file
, "inline-unit-growth limit reached.\n");
1044 fibheap_delete (heap
);
1048 /* Decide on the inlining. We do so in the topological order to avoid
1049 expenses on updating datastructures. */
1052 cgraph_decide_inlining (void)
1054 struct cgraph_node
*node
;
1056 struct cgraph_node
**order
=
1057 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1058 struct cgraph_node
**inlined
=
1059 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1060 struct cgraph_node
**inlined_callees
=
1061 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1063 int ninlined_callees
;
1066 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1067 initial_insns
+= node
->local
.self_insns
;
1068 overall_insns
= initial_insns
;
1070 nnodes
= cgraph_postorder (order
);
1072 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1075 if (cgraph_dump_file
)
1076 fprintf (cgraph_dump_file
, "\n\nDeciding on always_inline functions:\n");
1078 /* In the first pass mark all always_inline edges. Do this with a priority
1079 so no our decisions makes this impossible. */
1080 for (i
= nnodes
- 1; i
>= 0; i
--)
1082 struct cgraph_edge
*e
;
1086 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1087 if (e
->callee
->local
.disregard_inline_limits
)
1091 if (cgraph_dump_file
)
1092 fprintf (cgraph_dump_file
,
1093 "Considering %s %i insns (always inline)\n",
1094 cgraph_node_name (node
), node
->global
.insns
);
1095 ninlined
= cgraph_inlined_into (order
[i
], inlined
);
1096 for (; e
; e
= e
->next_callee
)
1098 if (e
->inline_call
|| !e
->callee
->local
.disregard_inline_limits
)
1100 if (e
->callee
->output
|| e
->callee
== node
)
1103 cgraph_inlined_callees (e
->callee
, inlined_callees
);
1104 cgraph_mark_inline (node
, e
->callee
, inlined
, ninlined
,
1105 inlined_callees
, ninlined_callees
);
1106 for (y
= 0; y
< ninlined_callees
; y
++)
1107 inlined_callees
[y
]->output
= 0, node
->aux
= 0;
1108 if (cgraph_dump_file
)
1109 fprintf (cgraph_dump_file
, "Inlined %i times. Now %i insns\n\n",
1110 node
->global
.cloned_times
, overall_insns
);
1112 for (y
= 0; y
< ninlined
; y
++)
1113 inlined
[y
]->output
= 0, node
->aux
= 0;
1116 cgraph_decide_inlining_of_small_functions (inlined
, inlined_callees
);
1118 if (cgraph_dump_file
)
1119 fprintf (cgraph_dump_file
, "\n\nFunctions to inline once:\n");
1121 /* And finally decide what functions are called once. */
1123 for (i
= nnodes
- 1; i
>= 0; i
--)
1127 if (node
->callers
&& !node
->callers
->next_caller
&& !node
->needed
1128 && node
->local
.inlinable
&& !node
->callers
->inline_call
1129 && !DECL_EXTERNAL (node
->decl
) && !DECL_COMDAT (node
->decl
))
1132 struct cgraph_node
*node1
;
1134 /* Verify that we won't duplicate the caller. */
1135 for (node1
= node
->callers
->caller
;
1136 node1
->callers
&& node1
->callers
->inline_call
1137 && ok
; node1
= node1
->callers
->caller
)
1138 if (node1
->callers
->next_caller
|| node1
->needed
)
1142 if (cgraph_dump_file
)
1143 fprintf (cgraph_dump_file
,
1144 "Considering %s %i insns (called once)\n",
1145 cgraph_node_name (node
), node
->global
.insns
);
1146 ninlined
= cgraph_inlined_into (node
->callers
->caller
, inlined
);
1147 if (cgraph_check_inline_limits
1148 (node
->callers
->caller
, node
, inlined
, ninlined
))
1151 cgraph_inlined_callees (node
, inlined_callees
);
1152 cgraph_mark_inline (node
->callers
->caller
, node
, inlined
,
1153 ninlined
, inlined_callees
,
1155 for (y
= 0; y
< ninlined_callees
; y
++)
1156 inlined_callees
[y
]->output
= 0, node
->aux
= 0;
1157 if (cgraph_dump_file
)
1158 fprintf (cgraph_dump_file
, "Inlined. Now %i insns\n\n", overall_insns
);
1160 for (y
= 0; y
< ninlined
; y
++)
1161 inlined
[y
]->output
= 0, node
->aux
= 0;
1166 if (cgraph_dump_file
)
1167 fprintf (cgraph_dump_file
,
1168 "\nInlined %i calls, elliminated %i functions, %i insns turned to %i insns.\n",
1169 ncalls_inlined
, nfunctions_inlined
, initial_insns
,
1173 free (inlined_callees
);
1176 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
1179 cgraph_inline_p (tree caller_decl
, tree callee_decl
)
1181 struct cgraph_node
*caller
= cgraph_node (caller_decl
);
1182 struct cgraph_node
*callee
= cgraph_node (callee_decl
);
1183 struct cgraph_edge
*e
;
1185 for (e
= caller
->callees
; e
; e
= e
->next_callee
)
1186 if (e
->callee
== callee
)
1187 return e
->inline_call
;
1188 /* We do not record builtins in the callgraph. Perhaps it would make more
1189 sense to do so and then prune out those not overwritten by explicit
1193 /* Expand all functions that must be output.
1195 Attempt to topologically sort the nodes so function is output when
1196 all called functions are already assembled to allow data to be
1197 propagated across the callgraph. Use a stack to get smaller distance
1198 between a function and it's callees (later we may choose to use a more
1199 sophisticated algorithm for function reordering; we will likely want
1200 to use subsections to make the output functions appear in top-down
1204 cgraph_expand_functions (void)
1206 struct cgraph_node
*node
;
1207 struct cgraph_node
**order
=
1208 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1212 cgraph_mark_functions_to_output ();
1214 order_pos
= cgraph_postorder (order
);
1216 for (i
= order_pos
- 1; i
>= 0; i
--)
1221 if (!node
->reachable
)
1224 cgraph_expand_function (node
);
1230 /* Mark all local functions.
1232 A local function is one whose calls can occur only in the
1233 current compilation unit, so we change its calling convention.
1234 We simply mark all static functions whose address is not taken
1238 cgraph_mark_local_functions (void)
1240 struct cgraph_node
*node
;
1242 if (cgraph_dump_file
)
1243 fprintf (cgraph_dump_file
, "Marking local functions:");
1245 /* Figure out functions we want to assemble. */
1246 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1248 node
->local
.local
= (!node
->needed
1249 && DECL_SAVED_TREE (node
->decl
)
1250 && !TREE_PUBLIC (node
->decl
));
1251 if (cgraph_dump_file
&& node
->local
.local
)
1252 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
1254 if (cgraph_dump_file
)
1255 fprintf (cgraph_dump_file
, "\n");
1258 /* Perform simple optimizations based on callgraph. */
1261 cgraph_optimize (void)
1263 if (!flag_unit_at_a_time
)
1265 timevar_push (TV_CGRAPHOPT
);
1267 fprintf (stderr
, "Performing intraprocedural optimizations\n");
1268 if (cgraph_dump_file
)
1270 fprintf (cgraph_dump_file
, "Initial callgraph:");
1271 dump_cgraph (cgraph_dump_file
);
1273 cgraph_mark_local_functions ();
1275 cgraph_decide_inlining ();
1277 cgraph_global_info_ready
= true;
1278 if (cgraph_dump_file
)
1280 fprintf (cgraph_dump_file
, "Optimized callgraph:");
1281 dump_cgraph (cgraph_dump_file
);
1283 timevar_pop (TV_CGRAPHOPT
);
1285 fprintf (stderr
, "Assembling functions:");
1287 /* Output everything. */
1288 cgraph_expand_functions ();
1289 if (cgraph_dump_file
)
1291 fprintf (cgraph_dump_file
, "Final callgraph:");
1292 dump_cgraph (cgraph_dump_file
);