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_all_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 necessary. */
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 eliminated 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. */
127 cgraph_assemble_pending_functions (void)
131 if (flag_unit_at_a_time
)
134 while (cgraph_nodes_queue
)
136 struct cgraph_node
*n
= cgraph_nodes_queue
;
138 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
139 if (!n
->origin
&& !DECL_EXTERNAL (n
->decl
))
141 cgraph_expand_function (n
);
149 /* DECL has been parsed. Take it, queue it, compile it at the whim of the
150 logic in effect. If NESTED is true, then our caller cannot stand to have
151 the garbage collector run at the moment. We would need to either create
152 a new GC context, or just not compile right now. */
155 cgraph_finalize_function (tree decl
, bool nested
)
157 struct cgraph_node
*node
= cgraph_node (decl
);
159 if (node
->local
.finalized
)
161 /* As an GCC extension we allow redefinition of the function. The
162 semantics when both copies of bodies differ is not well defined.
163 We replace the old body with new body so in unit at a time mode
164 we always use new body, while in normal mode we may end up with
165 old body inlined into some functions and new body expanded and
168 ??? It may make more sense to use one body for inlining and other
169 body for expanding the function but this is difficult to do. */
171 /* If node->output is set, then this is a unit-at-a-time compilation
172 and we have already begun whole-unit analysis. This is *not*
173 testing for whether we've already emitted the function. That
174 case can be sort-of legitimately seen with real function
175 redefinition errors. I would argue that the front end should
176 never present us with such a case, but don't enforce that for now. */
180 /* Reset our datastructures so we can analyze the function again. */
181 memset (&node
->local
, 0, sizeof (node
->local
));
182 memset (&node
->global
, 0, sizeof (node
->global
));
183 memset (&node
->rtl
, 0, sizeof (node
->rtl
));
184 node
->analyzed
= false;
185 while (node
->callees
)
186 cgraph_remove_edge (node
, node
->callees
->callee
);
188 /* We may need to re-queue the node for assembling in case
189 we already proceeded it and ignored as not needed. */
190 if (node
->reachable
&& !flag_unit_at_a_time
)
192 struct cgraph_node
*n
;
194 for (n
= cgraph_nodes_queue
; n
; n
= n
->next_needed
)
202 notice_global_symbol (decl
);
204 node
->local
.finalized
= true;
206 /* If not unit at a time, then we need to create the call graph
207 now, so that called functions can be queued and emitted now. */
208 if (!flag_unit_at_a_time
)
209 cgraph_analyze_function (node
);
211 if (decide_is_function_needed (node
, decl
))
212 cgraph_mark_needed_node (node
);
214 /* If not unit at a time, go ahead and emit everything we've found
215 to be reachable at this time. */
217 cgraph_assemble_pending_functions ();
219 /* If we've not yet emitted decl, tell the debug info about it. */
220 if (!TREE_ASM_WRITTEN (decl
))
221 (*debug_hooks
->deferred_inline_function
) (decl
);
224 /* Walk tree and record all calls. Called via walk_tree. */
226 record_call_1 (tree
*tp
, int *walk_subtrees
, void *data
)
230 switch (TREE_CODE (t
))
233 /* ??? Really, we should mark this decl as *potentially* referenced
234 by this function and re-examine whether the decl is actually used
235 after rtl has been generated. */
237 cgraph_varpool_mark_needed_node (cgraph_varpool_node (t
));
241 if (flag_unit_at_a_time
)
243 /* Record dereferences to the functions. This makes the
244 functions reachable unconditionally. */
245 tree decl
= TREE_OPERAND (*tp
, 0);
246 if (TREE_CODE (decl
) == FUNCTION_DECL
)
247 cgraph_mark_needed_node (cgraph_node (decl
));
253 tree decl
= get_callee_fndecl (*tp
);
254 if (decl
&& TREE_CODE (decl
) == FUNCTION_DECL
)
256 if (DECL_BUILT_IN (decl
))
258 cgraph_record_call (data
, decl
);
260 /* When we see a function call, we don't want to look at the
261 function reference in the ADDR_EXPR that is hanging from
262 the CALL_EXPR we're examining here, because we would
263 conclude incorrectly that the function's address could be
264 taken by something that is not a function call. So only
265 walk the function parameter list, skip the other subtrees. */
267 walk_tree (&TREE_OPERAND (*tp
, 1), record_call_1
, data
,
275 /* Save some cycles by not walking types and declaration as we
276 won't find anything useful there anyway. */
277 if (DECL_P (*tp
) || TYPE_P (*tp
))
283 if ((unsigned int) TREE_CODE (t
) >= LAST_AND_UNUSED_TREE_CODE
)
284 return (*lang_hooks
.callgraph
.analyze_expr
) (tp
, walk_subtrees
, data
);
291 /* Create cgraph edges for function calls inside BODY from DECL. */
294 cgraph_create_edges (tree decl
, tree body
)
296 /* The nodes we're interested in are never shared, so walk
297 the tree ignoring duplicates. */
298 visited_nodes
= htab_create (37, htab_hash_pointer
,
299 htab_eq_pointer
, NULL
);
300 walk_tree (&body
, record_call_1
, decl
, visited_nodes
);
301 htab_delete (visited_nodes
);
302 visited_nodes
= NULL
;
305 /* Analyze the function scheduled to be output. */
307 cgraph_analyze_function (struct cgraph_node
*node
)
309 tree decl
= node
->decl
;
311 current_function_decl
= decl
;
313 /* First kill forward declaration so reverse inlining works properly. */
314 cgraph_create_edges (decl
, DECL_SAVED_TREE (decl
));
316 node
->local
.inlinable
= tree_inlinable_function_p (decl
);
317 if (!DECL_ESTIMATED_INSNS (decl
))
318 DECL_ESTIMATED_INSNS (decl
)
319 = (*lang_hooks
.tree_inlining
.estimate_num_insns
) (decl
);
320 node
->local
.self_insns
= DECL_ESTIMATED_INSNS (decl
);
321 if (node
->local
.inlinable
)
322 node
->local
.disregard_inline_limits
323 = (*lang_hooks
.tree_inlining
.disregard_inline_limits
) (decl
);
325 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
326 node
->global
.insns
= node
->local
.self_insns
;
327 if (!DECL_EXTERNAL (decl
))
329 node
->global
.cloned_times
= 1;
330 node
->global
.will_be_output
= true;
333 node
->analyzed
= true;
334 current_function_decl
= NULL
;
337 /* Analyze the whole compilation unit once it is parsed completely. */
340 cgraph_finalize_compilation_unit (void)
342 struct cgraph_node
*node
;
344 if (!flag_unit_at_a_time
)
346 cgraph_assemble_pending_functions ();
350 cgraph_varpool_assemble_pending_decls ();
352 fprintf (stderr
, "\nAnalyzing compilation unit\n");
354 timevar_push (TV_CGRAPH
);
355 if (cgraph_dump_file
)
357 fprintf (cgraph_dump_file
, "Initial entry points:");
358 for (node
= cgraph_nodes
; node
; node
= node
->next
)
359 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
360 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
361 fprintf (cgraph_dump_file
, "\n");
364 /* Propagate reachability flag and lower representation of all reachable
365 functions. In the future, lowering will introduce new functions and
366 new entry points on the way (by template instantiation and virtual
367 method table generation for instance). */
368 while (cgraph_nodes_queue
)
370 struct cgraph_edge
*edge
;
371 tree decl
= cgraph_nodes_queue
->decl
;
373 node
= cgraph_nodes_queue
;
374 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
376 /* ??? It is possible to create extern inline function and later using
377 weak alas attribute to kill it's body. See
378 gcc.c-torture/compile/20011119-1.c */
379 if (!DECL_SAVED_TREE (decl
))
382 if (node
->analyzed
|| !node
->reachable
|| !DECL_SAVED_TREE (decl
))
385 cgraph_analyze_function (node
);
387 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
388 if (!edge
->callee
->reachable
)
389 cgraph_mark_reachable_node (edge
->callee
);
391 cgraph_varpool_assemble_pending_decls ();
394 /* Collect entry points to the unit. */
396 if (cgraph_dump_file
)
398 fprintf (cgraph_dump_file
, "Unit entry points:");
399 for (node
= cgraph_nodes
; node
; node
= node
->next
)
400 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
401 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
402 fprintf (cgraph_dump_file
, "\n\nInitial ");
403 dump_cgraph (cgraph_dump_file
);
406 if (cgraph_dump_file
)
407 fprintf (cgraph_dump_file
, "\nReclaiming functions:");
409 for (node
= cgraph_nodes
; node
; node
= node
->next
)
411 tree decl
= node
->decl
;
413 if (!node
->reachable
&& DECL_SAVED_TREE (decl
))
415 cgraph_remove_node (node
);
416 if (cgraph_dump_file
)
417 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
420 if (cgraph_dump_file
)
422 fprintf (cgraph_dump_file
, "\n\nReclaimed ");
423 dump_cgraph (cgraph_dump_file
);
426 timevar_pop (TV_CGRAPH
);
429 /* Figure out what functions we want to assemble. */
432 cgraph_mark_functions_to_output (void)
434 struct cgraph_node
*node
;
436 for (node
= cgraph_nodes
; node
; node
= node
->next
)
438 tree decl
= node
->decl
;
439 struct cgraph_edge
*e
;
443 for (e
= node
->callers
; e
; e
= e
->next_caller
)
447 /* We need to output all local functions that are used and not
448 always inlined, as well as those that are reachable from
449 outside the current compilation unit. */
450 if (DECL_SAVED_TREE (decl
)
452 || (e
&& node
->reachable
))
453 && !TREE_ASM_WRITTEN (decl
) && !node
->origin
454 && !DECL_EXTERNAL (decl
))
459 /* Optimize the function before expansion. */
462 cgraph_optimize_function (struct cgraph_node
*node
)
464 tree decl
= node
->decl
;
466 timevar_push (TV_INTEGRATION
);
467 /* optimize_inline_calls avoids inlining of current_function_decl. */
468 current_function_decl
= decl
;
469 if (flag_inline_trees
)
470 optimize_inline_calls (decl
);
473 for (node
= node
->nested
; node
; node
= node
->next_nested
)
474 cgraph_optimize_function (node
);
476 timevar_pop (TV_INTEGRATION
);
479 /* Expand function specified by NODE. */
482 cgraph_expand_function (struct cgraph_node
*node
)
484 tree decl
= node
->decl
;
485 struct cgraph_edge
*e
;
487 if (flag_unit_at_a_time
)
488 announce_function (decl
);
490 cgraph_optimize_function (node
);
492 /* Generate RTL for the body of DECL. Nested functions are expanded
493 via lang_expand_decl_stmt. */
494 (*lang_hooks
.callgraph
.expand_function
) (decl
);
496 if (!flag_unit_at_a_time
)
498 if (!node
->local
.inlinable
499 || (!node
->local
.disregard_inline_limits
500 && !cgraph_default_inline_p (node
)))
501 DECL_SAVED_TREE (node
->decl
) = NULL
;
505 for (e
= node
->callers
; e
; e
= e
->next_caller
)
509 DECL_SAVED_TREE (decl
) = NULL
;
511 current_function_decl
= NULL
;
514 /* Fill array order with all nodes with output flag set in the reverse
515 topological order. */
517 cgraph_postorder (struct cgraph_node
**order
)
519 struct cgraph_node
*node
, *node2
;
522 struct cgraph_edge
*edge
, last
;
524 struct cgraph_node
**stack
=
525 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
527 /* We have to deal with cycles nicely, so use a depth first traversal
528 output algorithm. Ignore the fact that some functions won't need
529 to be output and put them into order as well, so we get dependencies
530 right through intline functions. */
531 for (node
= cgraph_nodes
; node
; node
= node
->next
)
533 for (node
= cgraph_nodes
; node
; node
= node
->next
)
540 node
->aux
= node
->callers
;
543 while (node2
->aux
!= &last
)
546 if (edge
->next_caller
)
547 node2
->aux
= edge
->next_caller
;
550 if (!edge
->caller
->aux
)
552 if (!edge
->caller
->callers
)
553 edge
->caller
->aux
= &last
;
555 edge
->caller
->aux
= edge
->caller
->callers
;
556 stack
[stack_size
++] = node2
;
557 node2
= edge
->caller
;
561 if (node2
->aux
== &last
)
563 order
[order_pos
++] = node2
;
565 node2
= stack
[--stack_size
];
575 #define INLINED_TIMES(node) ((size_t)(node)->aux)
576 #define SET_INLINED_TIMES(node,times) ((node)->aux = (void *)(times))
578 /* Return list of nodes we decided to inline NODE into, set their output
579 flag and compute INLINED_TIMES.
581 We do simple backtracing to get INLINED_TIMES right. This should not be
582 expensive as we limit the amount of inlining. Alternatively we may first
583 discover set of nodes, topologically sort these and propagate
587 cgraph_inlined_into (struct cgraph_node
*node
, struct cgraph_node
**array
)
590 struct cgraph_edge
**stack
;
591 struct cgraph_edge
*e
, *e1
;
595 /* Fast path: since we traverse in mostly topological order, we will likely
597 for (e
= node
->callers
; e
; e
= e
->next_caller
)
604 /* Allocate stack for back-tracking up callgraph. */
605 stack
= xmalloc ((cgraph_n_nodes
+ 1) * sizeof (struct cgraph_edge
));
608 /* Push the first edge on to the stack. */
613 struct cgraph_node
*caller
;
615 /* Look at the edge on the top of the stack. */
619 /* Check if the caller destination has been visited yet. */
622 array
[nfound
++] = e
->caller
;
623 /* Mark that we have visited the destination. */
624 caller
->output
= true;
625 SET_INLINED_TIMES (caller
, 0);
627 SET_INLINED_TIMES (caller
, INLINED_TIMES (caller
) + 1);
629 for (e1
= caller
->callers
; e1
; e1
= e1
->next_caller
)
638 for (e1
= e
->next_caller
; e1
; e1
= e1
->next_caller
)
661 if (cgraph_dump_file
)
663 fprintf (cgraph_dump_file
, " Found inline predecesors of %s:",
664 cgraph_node_name (node
));
665 for (i
= 0; i
< nfound
; i
++)
667 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (array
[i
]));
668 if (INLINED_TIMES (array
[i
]) != 1)
669 fprintf (cgraph_dump_file
, " (%i times)",
670 (int)INLINED_TIMES (array
[i
]));
672 fprintf (cgraph_dump_file
, "\n");
678 /* Return list of nodes we decided to inline into NODE, set their output
679 flag and compute INLINED_TIMES.
681 This function is identical to cgraph_inlined_into with callers and callees
685 cgraph_inlined_callees (struct cgraph_node
*node
, struct cgraph_node
**array
)
688 struct cgraph_edge
**stack
;
689 struct cgraph_edge
*e
, *e1
;
693 /* Fast path: since we traverse in mostly topological order, we will likely
695 for (e
= node
->callees
; e
; e
= e
->next_callee
)
702 /* Allocate stack for back-tracking up callgraph. */
703 stack
= xmalloc ((cgraph_n_nodes
+ 1) * sizeof (struct cgraph_edge
));
706 /* Push the first edge on to the stack. */
711 struct cgraph_node
*callee
;
713 /* Look at the edge on the top of the stack. */
717 /* Check if the callee destination has been visited yet. */
720 array
[nfound
++] = e
->callee
;
721 /* Mark that we have visited the destination. */
722 callee
->output
= true;
723 SET_INLINED_TIMES (callee
, 0);
725 SET_INLINED_TIMES (callee
, INLINED_TIMES (callee
) + 1);
727 for (e1
= callee
->callees
; e1
; e1
= e1
->next_callee
)
736 for (e1
= e
->next_callee
; e1
; e1
= e1
->next_callee
)
758 if (cgraph_dump_file
)
760 fprintf (cgraph_dump_file
, " Found inline successors of %s:",
761 cgraph_node_name (node
));
762 for (i
= 0; i
< nfound
; i
++)
764 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (array
[i
]));
765 if (INLINED_TIMES (array
[i
]) != 1)
766 fprintf (cgraph_dump_file
, " (%i times)",
767 (int)INLINED_TIMES (array
[i
]));
769 fprintf (cgraph_dump_file
, "\n");
775 /* Estimate size of the function after inlining WHAT into TO. */
778 cgraph_estimate_size_after_inlining (int times
, struct cgraph_node
*to
,
779 struct cgraph_node
*what
)
781 return (what
->global
.insns
- INSNS_PER_CALL
) * times
+ to
->global
.insns
;
784 /* Estimate the growth caused by inlining NODE into all callees. */
787 cgraph_estimate_growth (struct cgraph_node
*node
)
791 int clones_added
= 0;
792 struct cgraph_edge
*e
;
794 for (e
= node
->callers
; e
; e
= e
->next_caller
)
797 growth
+= ((cgraph_estimate_size_after_inlining (1, e
->caller
, node
)
799 e
->caller
->global
.insns
) *e
->caller
->global
.cloned_times
);
800 calls_saved
+= e
->caller
->global
.cloned_times
;
801 clones_added
+= e
->caller
->global
.cloned_times
;
804 /* ??? Wrong for self recursive functions or cases where we decide to not
805 inline for different reasons, but it is not big deal as in that case
806 we will keep the body around, but we will also avoid some inlining. */
807 if (!node
->needed
&& !node
->origin
&& !DECL_EXTERNAL (node
->decl
))
808 growth
-= node
->global
.insns
, clones_added
--;
816 /* Update insn sizes after inlining WHAT into TO that is already inlined into
817 all nodes in INLINED array. */
820 cgraph_mark_inline (struct cgraph_node
*to
, struct cgraph_node
*what
,
821 struct cgraph_node
**inlined
, int ninlined
,
822 struct cgraph_node
**inlined_callees
,
823 int ninlined_callees
)
828 struct cgraph_edge
*e
;
832 for (e
= what
->callers
; e
; e
= e
->next_caller
)
838 e
->inline_call
= true;
840 clones
+= e
->caller
->global
.cloned_times
;
842 else if (!e
->inline_call
)
847 ncalls_inlined
+= times
;
849 new_insns
= cgraph_estimate_size_after_inlining (times
, to
, what
);
850 if (to
->global
.will_be_output
)
851 overall_insns
+= new_insns
- to
->global
.insns
;
852 to
->global
.insns
= new_insns
;
854 if (!called
&& !what
->needed
&& !what
->origin
855 && !DECL_EXTERNAL (what
->decl
))
857 if (!what
->global
.will_be_output
)
860 nfunctions_inlined
++;
861 what
->global
.will_be_output
= 0;
862 overall_insns
-= what
->global
.insns
;
864 what
->global
.cloned_times
+= clones
;
865 for (i
= 0; i
< ninlined
; i
++)
868 cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined
[i
]) *
869 times
, inlined
[i
], what
);
870 if (inlined
[i
]->global
.will_be_output
)
871 overall_insns
+= new_insns
- inlined
[i
]->global
.insns
;
872 inlined
[i
]->global
.insns
= new_insns
;
874 for (i
= 0; i
< ninlined_callees
; i
++)
876 inlined_callees
[i
]->global
.cloned_times
+=
877 INLINED_TIMES (inlined_callees
[i
]) * clones
;
881 /* Return false when inlining WHAT into TO is not good idea as it would cause
882 too large growth of function bodies. */
885 cgraph_check_inline_limits (struct cgraph_node
*to
, struct cgraph_node
*what
,
886 struct cgraph_node
**inlined
, int ninlined
)
890 struct cgraph_edge
*e
;
894 for (e
= to
->callees
; e
; e
= e
->next_callee
)
895 if (e
->callee
== what
)
898 /* When inlining large function body called once into small function,
899 take the inlined function as base for limiting the growth. */
900 if (to
->local
.self_insns
> what
->local
.self_insns
)
901 limit
= to
->local
.self_insns
;
903 limit
= what
->local
.self_insns
;
905 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
907 newsize
= cgraph_estimate_size_after_inlining (times
, to
, what
);
908 if (newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
911 for (i
= 0; i
< ninlined
; i
++)
914 cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined
[i
]) *
915 times
, inlined
[i
], what
);
916 if (newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
918 inlined
[i
]->local
.self_insns
*
919 (100 + PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
)) / 100)
925 /* Return true when function N is small enough to be inlined. */
928 cgraph_default_inline_p (struct cgraph_node
*n
)
930 if (!DECL_INLINE (n
->decl
) || !DECL_SAVED_TREE (n
->decl
))
932 if (DECL_DECLARED_INLINE_P (n
->decl
))
933 return n
->global
.insns
< MAX_INLINE_INSNS_SINGLE
;
935 return n
->global
.insns
< MAX_INLINE_INSNS_AUTO
;
938 /* We use greedy algorithm for inlining of small functions:
939 All inline candidates are put into prioritized heap based on estimated
940 growth of the overall number of instructions and then update the estimates.
942 INLINED and INLINED_CALEES are just pointers to arrays large enought
943 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
946 cgraph_decide_inlining_of_small_functions (struct cgraph_node
**inlined
,
947 struct cgraph_node
**inlined_callees
)
950 struct cgraph_node
*node
;
951 fibheap_t heap
= fibheap_new ();
952 struct fibnode
**heap_node
=
953 xcalloc (cgraph_max_uid
, sizeof (struct fibnode
*));
954 int ninlined
, ninlined_callees
;
955 int max_insns
= ((HOST_WIDEST_INT
) initial_insns
956 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
958 /* Put all inline candidates into the heap. */
960 for (node
= cgraph_nodes
; node
; node
= node
->next
)
962 struct cgraph_edge
*e
;
964 if (!node
->local
.inlinable
|| !node
->callers
965 || !cgraph_default_inline_p (node
))
968 /* Rule out always_inline functions we dealt with earlier. */
969 for (e
= node
->callers
; e
; e
= e
->next_caller
)
974 heap_node
[node
->uid
] =
975 fibheap_insert (heap
, cgraph_estimate_growth (node
), node
);
978 if (cgraph_dump_file
)
979 fprintf (cgraph_dump_file
, "\nDeciding on smaller functions:\n");
980 while ((node
= fibheap_extract_min (heap
)) && overall_insns
<= max_insns
)
982 struct cgraph_edge
*e
;
983 int old_insns
= overall_insns
;
985 heap_node
[node
->uid
] = NULL
;
986 if (cgraph_dump_file
)
987 fprintf (cgraph_dump_file
,
988 "\nConsidering %s with %i insns\n"
989 " Estimated growth is %+i insns.\n",
990 cgraph_node_name (node
), node
->global
.insns
,
991 cgraph_estimate_growth (node
));
992 if (!cgraph_default_inline_p (node
))
994 if (cgraph_dump_file
)
995 fprintf (cgraph_dump_file
, " Function too large.\n");
998 ninlined_callees
= cgraph_inlined_callees (node
, inlined_callees
);
999 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1000 if (!e
->inline_call
&& e
->caller
!= node
)
1002 ninlined
= cgraph_inlined_into (e
->caller
, inlined
);
1003 if (e
->callee
->output
1004 || !cgraph_check_inline_limits (e
->caller
, node
, inlined
,
1007 for (i
= 0; i
< ninlined
; i
++)
1008 inlined
[i
]->output
= 0, node
->aux
= 0;
1009 if (cgraph_dump_file
)
1010 fprintf (cgraph_dump_file
, " Not inlining into %s.\n",
1011 cgraph_node_name (e
->caller
));
1014 cgraph_mark_inline (e
->caller
, node
, inlined
, ninlined
,
1015 inlined_callees
, ninlined_callees
);
1016 if (heap_node
[e
->caller
->uid
])
1017 fibheap_replace_key (heap
, heap_node
[e
->caller
->uid
],
1018 cgraph_estimate_growth (e
->caller
));
1020 /* Size of the functions we updated into has changed, so update
1022 for (i
= 0; i
< ninlined
; i
++)
1024 inlined
[i
]->output
= 0, node
->aux
= 0;
1025 if (heap_node
[inlined
[i
]->uid
])
1026 fibheap_replace_key (heap
, heap_node
[inlined
[i
]->uid
],
1027 cgraph_estimate_growth (inlined
[i
]));
1029 if (cgraph_dump_file
)
1030 fprintf (cgraph_dump_file
,
1031 " Inlined into %s which now has %i insns.\n",
1032 cgraph_node_name (e
->caller
),
1033 e
->caller
->global
.insns
);
1037 /* Similarly all functions called by the function we just inlined
1038 are now called more times; update keys. */
1040 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1041 if (!e
->inline_call
&& heap_node
[e
->callee
->uid
])
1042 fibheap_replace_key (heap
, heap_node
[e
->callee
->uid
],
1043 cgraph_estimate_growth (e
->callee
));
1045 for (i
= 0; i
< ninlined_callees
; i
++)
1047 struct cgraph_edge
*e
;
1049 for (e
= inlined_callees
[i
]->callees
; e
; e
= e
->next_callee
)
1050 if (!e
->inline_call
&& heap_node
[e
->callee
->uid
])
1051 fibheap_replace_key (heap
, heap_node
[e
->callee
->uid
],
1052 cgraph_estimate_growth (e
->callee
));
1054 inlined_callees
[i
]->output
= 0, node
->aux
= 0;
1056 if (cgraph_dump_file
)
1057 fprintf (cgraph_dump_file
,
1058 " Inlined %i times for a net change of %+i insns.\n",
1059 node
->global
.cloned_times
, overall_insns
- old_insns
);
1061 if (cgraph_dump_file
&& !fibheap_empty (heap
))
1062 fprintf (cgraph_dump_file
, "\nReached the inline-unit-growth limit.\n");
1063 fibheap_delete (heap
);
1067 /* Decide on the inlining. We do so in the topological order to avoid
1068 expenses on updating datastructures. */
1071 cgraph_decide_inlining (void)
1073 struct cgraph_node
*node
;
1075 struct cgraph_node
**order
=
1076 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1077 struct cgraph_node
**inlined
=
1078 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1079 struct cgraph_node
**inlined_callees
=
1080 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1082 int ninlined_callees
;
1086 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1087 initial_insns
+= node
->local
.self_insns
;
1088 overall_insns
= initial_insns
;
1090 nnodes
= cgraph_postorder (order
);
1092 if (cgraph_dump_file
)
1093 fprintf (cgraph_dump_file
,
1094 "\nDeciding on inlining. Starting with %i insns.\n",
1097 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1100 if (cgraph_dump_file
)
1101 fprintf (cgraph_dump_file
, "\nInlining always_inline functions:\n");
1103 /* In the first pass mark all always_inline edges. Do this with a priority
1104 so none of our later choices will make this impossible. */
1105 for (i
= nnodes
- 1; i
>= 0; i
--)
1107 struct cgraph_edge
*e
;
1111 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1112 if (e
->callee
->local
.disregard_inline_limits
)
1116 if (cgraph_dump_file
)
1117 fprintf (cgraph_dump_file
,
1118 "\nConsidering %s %i insns (always inline)\n",
1119 cgraph_node_name (e
->callee
), e
->callee
->global
.insns
);
1120 ninlined
= cgraph_inlined_into (order
[i
], inlined
);
1121 for (; e
; e
= e
->next_callee
)
1123 old_insns
= overall_insns
;
1124 if (e
->inline_call
|| !e
->callee
->local
.disregard_inline_limits
)
1126 if (e
->callee
->output
|| e
->callee
== node
)
1129 cgraph_inlined_callees (e
->callee
, inlined_callees
);
1130 cgraph_mark_inline (node
, e
->callee
, inlined
, ninlined
,
1131 inlined_callees
, ninlined_callees
);
1132 for (y
= 0; y
< ninlined_callees
; y
++)
1133 inlined_callees
[y
]->output
= 0, node
->aux
= 0;
1134 if (cgraph_dump_file
)
1135 fprintf (cgraph_dump_file
,
1136 " Inlined into %s which now has %i insns.\n",
1137 cgraph_node_name (node
->callees
->caller
),
1138 node
->callees
->caller
->global
.insns
);
1140 if (cgraph_dump_file
&& node
->global
.cloned_times
> 0)
1141 fprintf (cgraph_dump_file
,
1142 " Inlined %i times for a net change of %+i insns.\n",
1143 node
->global
.cloned_times
, overall_insns
- old_insns
);
1144 for (y
= 0; y
< ninlined
; y
++)
1145 inlined
[y
]->output
= 0, node
->aux
= 0;
1148 cgraph_decide_inlining_of_small_functions (inlined
, inlined_callees
);
1150 if (cgraph_dump_file
)
1151 fprintf (cgraph_dump_file
, "\nDeciding on functions called once:\n");
1153 /* And finally decide what functions are called once. */
1155 for (i
= nnodes
- 1; i
>= 0; i
--)
1159 if (node
->callers
&& !node
->callers
->next_caller
&& !node
->needed
1160 && node
->local
.inlinable
&& !node
->callers
->inline_call
1161 && !DECL_EXTERNAL (node
->decl
) && !DECL_COMDAT (node
->decl
))
1164 struct cgraph_node
*node1
;
1166 /* Verify that we won't duplicate the caller. */
1167 for (node1
= node
->callers
->caller
;
1168 node1
->callers
&& node1
->callers
->inline_call
1169 && ok
; node1
= node1
->callers
->caller
)
1170 if (node1
->callers
->next_caller
|| node1
->needed
)
1174 if (cgraph_dump_file
)
1175 fprintf (cgraph_dump_file
,
1176 "\nConsidering %s %i insns.\n"
1177 " Called once from %s %i insns.\n",
1178 cgraph_node_name (node
), node
->global
.insns
,
1179 cgraph_node_name (node
->callers
->caller
),
1180 node
->callers
->caller
->global
.insns
);
1181 ninlined
= cgraph_inlined_into (node
->callers
->caller
, inlined
);
1182 old_insns
= overall_insns
;
1183 if (cgraph_check_inline_limits
1184 (node
->callers
->caller
, node
, inlined
, ninlined
))
1187 cgraph_inlined_callees (node
, inlined_callees
);
1188 cgraph_mark_inline (node
->callers
->caller
, node
, inlined
,
1189 ninlined
, inlined_callees
,
1191 for (y
= 0; y
< ninlined_callees
; y
++)
1192 inlined_callees
[y
]->output
= 0, node
->aux
= 0;
1193 if (cgraph_dump_file
)
1194 fprintf (cgraph_dump_file
,
1195 " Inlined into %s which now has %i insns"
1196 " for a net change of %+i insns.\n",
1197 cgraph_node_name (node
->callers
->caller
),
1198 node
->callers
->caller
->global
.insns
,
1199 overall_insns
- old_insns
);
1203 if (cgraph_dump_file
)
1204 fprintf (cgraph_dump_file
,
1205 " Inline limit reached, not inlined.\n");
1207 for (y
= 0; y
< ninlined
; y
++)
1208 inlined
[y
]->output
= 0, node
->aux
= 0;
1213 if (cgraph_dump_file
)
1214 fprintf (cgraph_dump_file
,
1215 "\nInlined %i calls, eliminated %i functions, "
1216 "%i insns turned to %i insns.\n\n",
1217 ncalls_inlined
, nfunctions_inlined
, initial_insns
,
1221 free (inlined_callees
);
1224 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
1227 cgraph_inline_p (tree caller_decl
, tree callee_decl
)
1229 struct cgraph_node
*caller
= cgraph_node (caller_decl
);
1230 struct cgraph_node
*callee
= cgraph_node (callee_decl
);
1231 struct cgraph_edge
*e
;
1233 for (e
= caller
->callees
; e
; e
= e
->next_callee
)
1234 if (e
->callee
== callee
)
1235 return e
->inline_call
;
1236 /* We do not record builtins in the callgraph. Perhaps it would make more
1237 sense to do so and then prune out those not overwritten by explicit
1241 /* Expand all functions that must be output.
1243 Attempt to topologically sort the nodes so function is output when
1244 all called functions are already assembled to allow data to be
1245 propagated across the callgraph. Use a stack to get smaller distance
1246 between a function and it's callees (later we may choose to use a more
1247 sophisticated algorithm for function reordering; we will likely want
1248 to use subsections to make the output functions appear in top-down
1252 cgraph_expand_all_functions (void)
1254 struct cgraph_node
*node
;
1255 struct cgraph_node
**order
=
1256 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1260 cgraph_mark_functions_to_output ();
1262 order_pos
= cgraph_postorder (order
);
1264 for (i
= order_pos
- 1; i
>= 0; i
--)
1269 if (!node
->reachable
)
1272 cgraph_expand_function (node
);
1278 /* Mark all local functions.
1280 A local function is one whose calls can occur only in the
1281 current compilation unit, so we change its calling convention.
1282 We simply mark all static functions whose address is not taken
1286 cgraph_mark_local_functions (void)
1288 struct cgraph_node
*node
;
1290 if (cgraph_dump_file
)
1291 fprintf (cgraph_dump_file
, "\nMarking local functions:");
1293 /* Figure out functions we want to assemble. */
1294 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1296 node
->local
.local
= (!node
->needed
1297 && DECL_SAVED_TREE (node
->decl
)
1298 && !TREE_PUBLIC (node
->decl
));
1299 if (cgraph_dump_file
&& node
->local
.local
)
1300 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
1302 if (cgraph_dump_file
)
1303 fprintf (cgraph_dump_file
, "\n\n");
1306 /* Perform simple optimizations based on callgraph. */
1309 cgraph_optimize (void)
1311 if (!flag_unit_at_a_time
)
1313 timevar_push (TV_CGRAPHOPT
);
1315 fprintf (stderr
, "Performing intraprocedural optimizations\n");
1317 cgraph_mark_local_functions ();
1318 if (cgraph_dump_file
)
1320 fprintf (cgraph_dump_file
, "Marked ");
1321 dump_cgraph (cgraph_dump_file
);
1324 cgraph_decide_inlining ();
1325 cgraph_global_info_ready
= true;
1326 if (cgraph_dump_file
)
1328 fprintf (cgraph_dump_file
, "Optimized ");
1329 dump_cgraph (cgraph_dump_file
);
1331 timevar_pop (TV_CGRAPHOPT
);
1333 /* Output everything. */
1335 fprintf (stderr
, "Assembling functions:\n");
1336 cgraph_expand_all_functions ();
1337 if (cgraph_dump_file
)
1339 fprintf (cgraph_dump_file
, "\nFinal ");
1340 dump_cgraph (cgraph_dump_file
);