1 /* Callgraph based intraprocedural optimizations.
2 Copyright (C) 2003, 2004 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"
43 #define INSNS_PER_CALL 10
45 static void cgraph_expand_all_functions (void);
46 static void cgraph_mark_functions_to_output (void);
47 static void cgraph_expand_function (struct cgraph_node *);
48 static tree record_call_1 (tree *, int *, void *);
49 static void cgraph_mark_local_functions (void);
50 static void cgraph_optimize_function (struct cgraph_node *);
51 static bool cgraph_default_inline_p (struct cgraph_node *n);
52 static void cgraph_analyze_function (struct cgraph_node *node);
53 static void cgraph_decide_inlining_incrementally (struct cgraph_node *);
55 /* Statistics we collect about inlining algorithm. */
56 static int ncalls_inlined;
57 static int nfunctions_inlined;
58 static int initial_insns;
59 static int overall_insns;
61 /* Records tree nodes seen in cgraph_create_edges. Simply using
62 walk_tree_without_duplicates doesn't guarantee each node is visited
63 once because it gets a new htab upon each recursive call from
65 static htab_t visited_nodes;
67 /* Determine if function DECL is needed. That is, visible to something
68 either outside this translation unit, something magic in the system
69 configury, or (if not doing unit-at-a-time) to something we havn't
73 decide_is_function_needed (struct cgraph_node *node, tree decl)
75 /* If we decided it was needed before, but at the time we didn't have
76 the body of the function available, then it's still needed. We have
77 to go back and re-check its dependencies now. */
81 /* Externally visible functions must be output. The exception is
82 COMDAT functions that must be output only when they are needed. */
83 if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
86 /* Constructors and destructors are reachable from the runtime by
88 if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl))
91 /* If the user told us it is used, then it must be so. */
92 if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
95 /* ??? If the assembler name is set by hand, it is possible to assemble
96 the name later after finalizing the function and the fact is noticed
97 in assemble_name then. This is arguably a bug. */
98 if (DECL_ASSEMBLER_NAME_SET_P (decl)
99 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
102 if (flag_unit_at_a_time)
105 /* If not doing unit at a time, then we'll only defer this function
106 if its marked for inlining. Otherwise we want to emit it now. */
108 /* "extern inline" functions are never output locally. */
109 if (DECL_EXTERNAL (decl))
111 /* We want to emit COMDAT functions only when absolutely necessary. */
112 if (DECL_COMDAT (decl))
114 if (!DECL_INLINE (decl)
115 || (!node->local.disregard_inline_limits
116 /* When declared inline, defer even the uninlinable functions.
117 This allows them to be eliminated when unused. */
118 && !DECL_DECLARED_INLINE_P (decl)
119 && (!node->local.inlinable || !cgraph_default_inline_p (node))))
125 /* When not doing unit-at-a-time, output all functions enqueued.
126 Return true when such a functions were found. */
129 cgraph_assemble_pending_functions (void)
133 if (flag_unit_at_a_time)
136 while (cgraph_nodes_queue)
138 struct cgraph_node *n = cgraph_nodes_queue;
140 cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
141 if (!n->origin && !DECL_EXTERNAL (n->decl))
143 cgraph_expand_function (n);
151 /* DECL has been parsed. Take it, queue it, compile it at the whim of the
152 logic in effect. If NESTED is true, then our caller cannot stand to have
153 the garbage collector run at the moment. We would need to either create
154 a new GC context, or just not compile right now. */
157 cgraph_finalize_function (tree decl, bool nested)
159 struct cgraph_node *node = cgraph_node (decl);
161 if (node->local.finalized)
163 /* As an GCC extension we allow redefinition of the function. The
164 semantics when both copies of bodies differ is not well defined.
165 We replace the old body with new body so in unit at a time mode
166 we always use new body, while in normal mode we may end up with
167 old body inlined into some functions and new body expanded and
170 ??? It may make more sense to use one body for inlining and other
171 body for expanding the function but this is difficult to do. */
173 /* If node->output is set, then this is a unit-at-a-time compilation
174 and we have already begun whole-unit analysis. This is *not*
175 testing for whether we've already emitted the function. That
176 case can be sort-of legitimately seen with real function
177 redefinition errors. I would argue that the front end should
178 never present us with such a case, but don't enforce that for now. */
182 /* Reset our datastructures so we can analyze the function again. */
183 memset (&node->local, 0, sizeof (node->local));
184 memset (&node->global, 0, sizeof (node->global));
185 memset (&node->rtl, 0, sizeof (node->rtl));
186 node->analyzed = false;
187 while (node->callees)
188 cgraph_remove_edge (node, node->callees->callee);
190 /* We may need to re-queue the node for assembling in case
191 we already proceeded it and ignored as not needed. */
192 if (node->reachable && !flag_unit_at_a_time)
194 struct cgraph_node *n;
196 for (n = cgraph_nodes_queue; n; n = n->next_needed)
204 notice_global_symbol (decl);
206 node->local.finalized = true;
208 /* If not unit at a time, then we need to create the call graph
209 now, so that called functions can be queued and emitted now. */
210 if (!flag_unit_at_a_time)
212 cgraph_analyze_function (node);
213 cgraph_decide_inlining_incrementally (node);
216 if (decide_is_function_needed (node, decl))
217 cgraph_mark_needed_node (node);
219 /* If not unit at a time, go ahead and emit everything we've found
220 to be reachable at this time. */
223 if (!cgraph_assemble_pending_functions ())
227 /* If we've not yet emitted decl, tell the debug info about it. */
228 if (!TREE_ASM_WRITTEN (decl))
229 (*debug_hooks->deferred_inline_function) (decl);
232 /* Walk tree and record all calls. Called via walk_tree. */
234 record_call_1 (tree *tp, int *walk_subtrees, void *data)
238 switch (TREE_CODE (t))
241 /* ??? Really, we should mark this decl as *potentially* referenced
242 by this function and re-examine whether the decl is actually used
243 after rtl has been generated. */
245 cgraph_varpool_mark_needed_node (cgraph_varpool_node (t));
249 if (flag_unit_at_a_time)
251 /* Record dereferences to the functions. This makes the
252 functions reachable unconditionally. */
253 tree decl = TREE_OPERAND (*tp, 0);
254 if (TREE_CODE (decl) == FUNCTION_DECL)
255 cgraph_mark_needed_node (cgraph_node (decl));
261 tree decl = get_callee_fndecl (*tp);
262 if (decl && TREE_CODE (decl) == FUNCTION_DECL)
264 cgraph_record_call (data, decl);
266 /* When we see a function call, we don't want to look at the
267 function reference in the ADDR_EXPR that is hanging from
268 the CALL_EXPR we're examining here, because we would
269 conclude incorrectly that the function's address could be
270 taken by something that is not a function call. So only
271 walk the function parameter list, skip the other subtrees. */
273 walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data,
281 /* Save some cycles by not walking types and declaration as we
282 won't find anything useful there anyway. */
283 if (DECL_P (*tp) || TYPE_P (*tp))
289 if ((unsigned int) TREE_CODE (t) >= LAST_AND_UNUSED_TREE_CODE)
290 return (*lang_hooks.callgraph.analyze_expr) (tp, walk_subtrees, data);
297 /* Create cgraph edges for function calls inside BODY from DECL. */
300 cgraph_create_edges (tree decl, tree body)
302 /* The nodes we're interested in are never shared, so walk
303 the tree ignoring duplicates. */
304 visited_nodes = htab_create (37, htab_hash_pointer,
305 htab_eq_pointer, NULL);
306 walk_tree (&body, record_call_1, decl, visited_nodes);
307 htab_delete (visited_nodes);
308 visited_nodes = NULL;
311 /* Analyze the function scheduled to be output. */
313 cgraph_analyze_function (struct cgraph_node *node)
315 tree decl = node->decl;
316 struct cgraph_edge *e;
318 current_function_decl = decl;
320 /* First kill forward declaration so reverse inlining works properly. */
321 cgraph_create_edges (decl, DECL_SAVED_TREE (decl));
323 node->local.inlinable = tree_inlinable_function_p (decl);
324 if (!DECL_ESTIMATED_INSNS (decl))
325 DECL_ESTIMATED_INSNS (decl)
326 = (*lang_hooks.tree_inlining.estimate_num_insns) (decl);
327 node->local.self_insns = DECL_ESTIMATED_INSNS (decl);
328 if (node->local.inlinable)
329 node->local.disregard_inline_limits
330 = (*lang_hooks.tree_inlining.disregard_inline_limits) (decl);
331 for (e = node->callers; e; e = e->next_caller)
332 if (e->inline_failed)
333 e->inline_failed = (!node->local.inlinable ? N_("function not inlinable")
334 : N_("function not considered for inlining"));
335 if (flag_really_no_inline && !node->local.disregard_inline_limits)
336 node->local.inlinable = 0;
337 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
338 node->global.insns = node->local.self_insns;
339 if (!DECL_EXTERNAL (decl))
341 node->global.cloned_times = 1;
342 node->global.will_be_output = true;
345 node->analyzed = true;
346 current_function_decl = NULL;
349 /* Analyze the whole compilation unit once it is parsed completely. */
352 cgraph_finalize_compilation_unit (void)
354 struct cgraph_node *node;
356 if (!flag_unit_at_a_time)
358 cgraph_assemble_pending_functions ();
362 cgraph_varpool_assemble_pending_decls ();
364 fprintf (stderr, "\nAnalyzing compilation unit\n");
366 timevar_push (TV_CGRAPH);
367 if (cgraph_dump_file)
369 fprintf (cgraph_dump_file, "Initial entry points:");
370 for (node = cgraph_nodes; node; node = node->next)
371 if (node->needed && DECL_SAVED_TREE (node->decl))
372 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
373 fprintf (cgraph_dump_file, "\n");
376 /* Propagate reachability flag and lower representation of all reachable
377 functions. In the future, lowering will introduce new functions and
378 new entry points on the way (by template instantiation and virtual
379 method table generation for instance). */
380 while (cgraph_nodes_queue)
382 struct cgraph_edge *edge;
383 tree decl = cgraph_nodes_queue->decl;
385 node = cgraph_nodes_queue;
386 cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
388 /* ??? It is possible to create extern inline function and later using
389 weak alas attribute to kill it's body. See
390 gcc.c-torture/compile/20011119-1.c */
391 if (!DECL_SAVED_TREE (decl))
394 if (node->analyzed || !node->reachable || !DECL_SAVED_TREE (decl))
397 cgraph_analyze_function (node);
399 for (edge = node->callees; edge; edge = edge->next_callee)
400 if (!edge->callee->reachable)
401 cgraph_mark_reachable_node (edge->callee);
403 cgraph_varpool_assemble_pending_decls ();
406 /* Collect entry points to the unit. */
408 if (cgraph_dump_file)
410 fprintf (cgraph_dump_file, "Unit entry points:");
411 for (node = cgraph_nodes; node; node = node->next)
412 if (node->needed && DECL_SAVED_TREE (node->decl))
413 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
414 fprintf (cgraph_dump_file, "\n\nInitial ");
415 dump_cgraph (cgraph_dump_file);
418 if (cgraph_dump_file)
419 fprintf (cgraph_dump_file, "\nReclaiming functions:");
421 for (node = cgraph_nodes; node; node = node->next)
423 tree decl = node->decl;
425 if (!node->reachable && DECL_SAVED_TREE (decl))
427 cgraph_remove_node (node);
428 if (cgraph_dump_file)
429 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
432 if (cgraph_dump_file)
434 fprintf (cgraph_dump_file, "\n\nReclaimed ");
435 dump_cgraph (cgraph_dump_file);
438 timevar_pop (TV_CGRAPH);
441 /* Figure out what functions we want to assemble. */
444 cgraph_mark_functions_to_output (void)
446 struct cgraph_node *node;
448 for (node = cgraph_nodes; node; node = node->next)
450 tree decl = node->decl;
451 struct cgraph_edge *e;
456 for (e = node->callers; e; e = e->next_caller)
457 if (e->inline_failed)
460 /* We need to output all local functions that are used and not
461 always inlined, as well as those that are reachable from
462 outside the current compilation unit. */
463 if (DECL_SAVED_TREE (decl)
465 || (e && node->reachable))
466 && !TREE_ASM_WRITTEN (decl) && !node->origin
467 && !DECL_EXTERNAL (decl))
472 /* Optimize the function before expansion. */
475 cgraph_optimize_function (struct cgraph_node *node)
477 tree decl = node->decl;
479 timevar_push (TV_INTEGRATION);
480 /* optimize_inline_calls avoids inlining of current_function_decl. */
481 current_function_decl = decl;
482 if (flag_inline_trees)
484 struct cgraph_edge *e;
486 for (e = node->callees; e; e = e->next_callee)
487 if (!e->inline_failed || warn_inline
488 || (DECL_DECLARED_INLINE_P (e->callee->decl)
489 && lookup_attribute ("always_inline",
490 DECL_ATTRIBUTES (e->callee->decl))))
493 optimize_inline_calls (decl);
497 for (node = node->nested; node; node = node->next_nested)
498 cgraph_optimize_function (node);
500 timevar_pop (TV_INTEGRATION);
503 /* Expand function specified by NODE. */
506 cgraph_expand_function (struct cgraph_node *node)
508 tree decl = node->decl;
510 if (flag_unit_at_a_time)
511 announce_function (decl);
513 cgraph_optimize_function (node);
515 /* Generate RTL for the body of DECL. Nested functions are expanded
516 via lang_expand_decl_stmt. */
517 (*lang_hooks.callgraph.expand_function) (decl);
519 if (!cgraph_function_possibly_inlined_p (decl))
520 DECL_SAVED_TREE (decl) = NULL;
521 current_function_decl = NULL;
524 /* Fill array order with all nodes with output flag set in the reverse
525 topological order. */
528 cgraph_postorder (struct cgraph_node **order)
530 struct cgraph_node *node, *node2;
533 struct cgraph_edge *edge, last;
535 struct cgraph_node **stack =
536 xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
538 /* We have to deal with cycles nicely, so use a depth first traversal
539 output algorithm. Ignore the fact that some functions won't need
540 to be output and put them into order as well, so we get dependencies
541 right through intline functions. */
542 for (node = cgraph_nodes; node; node = node->next)
544 for (node = cgraph_nodes; node; node = node->next)
551 node->aux = node->callers;
554 while (node2->aux != &last)
557 if (edge->next_caller)
558 node2->aux = edge->next_caller;
561 if (!edge->caller->aux)
563 if (!edge->caller->callers)
564 edge->caller->aux = &last;
566 edge->caller->aux = edge->caller->callers;
567 stack[stack_size++] = node2;
568 node2 = edge->caller;
572 if (node2->aux == &last)
574 order[order_pos++] = node2;
576 node2 = stack[--stack_size];
586 #define INLINED_TIMES(node) ((size_t)(node)->aux)
587 #define SET_INLINED_TIMES(node,times) ((node)->aux = (void *)(times))
589 /* Return list of nodes we decided to inline NODE into, set their output
590 flag and compute INLINED_TIMES.
592 We do simple backtracing to get INLINED_TIMES right. This should not be
593 expensive as we limit the amount of inlining. Alternatively we may first
594 discover set of nodes, topologically sort these and propagate
598 cgraph_inlined_into (struct cgraph_node *node, struct cgraph_node **array)
601 struct cgraph_edge **stack;
602 struct cgraph_edge *e, *e1;
606 /* Fast path: since we traverse in mostly topological order, we will likely
608 for (e = node->callers; e; e = e->next_caller)
609 if (!e->inline_failed)
615 /* Allocate stack for back-tracking up callgraph. */
616 stack = xmalloc ((cgraph_n_nodes + 1) * sizeof (struct cgraph_edge));
619 /* Push the first edge on to the stack. */
624 struct cgraph_node *caller;
626 /* Look at the edge on the top of the stack. */
630 /* Check if the caller destination has been visited yet. */
633 array[nfound++] = e->caller;
634 /* Mark that we have visited the destination. */
635 caller->output = true;
636 SET_INLINED_TIMES (caller, 0);
638 SET_INLINED_TIMES (caller, INLINED_TIMES (caller) + 1);
640 for (e1 = caller->callers; e1; e1 = e1->next_caller)
641 if (!e1->inline_failed)
650 for (e1 = e->next_caller; e1; e1 = e1->next_caller)
651 if (!e1->inline_failed)
673 if (cgraph_dump_file)
675 fprintf (cgraph_dump_file, " Found inline predecesors of %s:",
676 cgraph_node_name (node));
677 for (i = 0; i < nfound; i++)
679 fprintf (cgraph_dump_file, " %s", cgraph_node_name (array[i]));
680 if (INLINED_TIMES (array[i]) != 1)
681 fprintf (cgraph_dump_file, " (%i times)",
682 (int)INLINED_TIMES (array[i]));
684 fprintf (cgraph_dump_file, "\n");
690 /* Return list of nodes we decided to inline into NODE, set their output
691 flag and compute INLINED_TIMES.
693 This function is identical to cgraph_inlined_into with callers and callees
697 cgraph_inlined_callees (struct cgraph_node *node, struct cgraph_node **array)
700 struct cgraph_edge **stack;
701 struct cgraph_edge *e, *e1;
705 /* Fast path: since we traverse in mostly topological order, we will likely
707 for (e = node->callees; e; e = e->next_callee)
708 if (!e->inline_failed)
714 /* Allocate stack for back-tracking up callgraph. */
715 stack = xmalloc ((cgraph_n_nodes + 1) * sizeof (struct cgraph_edge));
718 /* Push the first edge on to the stack. */
723 struct cgraph_node *callee;
725 /* Look at the edge on the top of the stack. */
729 /* Check if the callee destination has been visited yet. */
732 array[nfound++] = e->callee;
733 /* Mark that we have visited the destination. */
734 callee->output = true;
735 SET_INLINED_TIMES (callee, 0);
737 SET_INLINED_TIMES (callee, INLINED_TIMES (callee) + 1);
739 for (e1 = callee->callees; e1; e1 = e1->next_callee)
740 if (!e1->inline_failed)
748 for (e1 = e->next_callee; e1; e1 = e1->next_callee)
749 if (!e1->inline_failed)
770 if (cgraph_dump_file)
772 fprintf (cgraph_dump_file, " Found inline successors of %s:",
773 cgraph_node_name (node));
774 for (i = 0; i < nfound; i++)
776 fprintf (cgraph_dump_file, " %s", cgraph_node_name (array[i]));
777 if (INLINED_TIMES (array[i]) != 1)
778 fprintf (cgraph_dump_file, " (%i times)",
779 (int)INLINED_TIMES (array[i]));
781 fprintf (cgraph_dump_file, "\n");
787 /* Estimate size of the function after inlining WHAT into TO. */
790 cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
791 struct cgraph_node *what)
793 return (what->global.insns - INSNS_PER_CALL) * times + to->global.insns;
796 /* Estimate the growth caused by inlining NODE into all callees. */
799 cgraph_estimate_growth (struct cgraph_node *node)
803 int clones_added = 0;
804 struct cgraph_edge *e;
806 for (e = node->callers; e; e = e->next_caller)
807 if (e->inline_failed)
809 growth += ((cgraph_estimate_size_after_inlining (1, e->caller, node)
811 e->caller->global.insns) *e->caller->global.cloned_times);
812 calls_saved += e->caller->global.cloned_times;
813 clones_added += e->caller->global.cloned_times;
816 /* ??? Wrong for self recursive functions or cases where we decide to not
817 inline for different reasons, but it is not big deal as in that case
818 we will keep the body around, but we will also avoid some inlining. */
819 if (!node->needed && !node->origin && !DECL_EXTERNAL (node->decl))
820 growth -= node->global.insns, clones_added--;
828 /* Update insn sizes after inlining WHAT into TO that is already inlined into
829 all nodes in INLINED array. */
832 cgraph_mark_inline (struct cgraph_node *to, struct cgraph_node *what,
833 struct cgraph_node **inlined, int ninlined,
834 struct cgraph_node **inlined_callees,
835 int ninlined_callees)
840 struct cgraph_edge *e;
844 what->global.inlined = 1;
845 for (e = what->callers; e; e = e->next_caller)
849 if (!e->inline_failed)
851 e->inline_failed = NULL;
853 clones += e->caller->global.cloned_times;
855 else if (e->inline_failed)
860 ncalls_inlined += times;
862 new_insns = cgraph_estimate_size_after_inlining (times, to, what);
863 if (to->global.will_be_output)
864 overall_insns += new_insns - to->global.insns;
865 to->global.insns = new_insns;
867 if (!called && !what->needed && !what->origin
868 && flag_unit_at_a_time
869 && !DECL_EXTERNAL (what->decl))
871 if (!what->global.will_be_output)
874 nfunctions_inlined++;
875 what->global.will_be_output = 0;
876 overall_insns -= what->global.insns;
878 what->global.cloned_times += clones;
879 for (i = 0; i < ninlined; i++)
882 cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined[i]) *
883 times, inlined[i], what);
884 if (inlined[i]->global.will_be_output)
885 overall_insns += new_insns - inlined[i]->global.insns;
886 inlined[i]->global.insns = new_insns;
888 for (i = 0; i < ninlined_callees; i++)
890 inlined_callees[i]->global.cloned_times +=
891 INLINED_TIMES (inlined_callees[i]) * clones;
895 /* Return false when inlining WHAT into TO is not good idea as it would cause
896 too large growth of function bodies. */
899 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
900 struct cgraph_node **inlined, int ninlined,
905 struct cgraph_edge *e;
909 for (e = to->callees; e; e = e->next_callee)
910 if (e->callee == what)
913 /* When inlining large function body called once into small function,
914 take the inlined function as base for limiting the growth. */
915 if (to->local.self_insns > what->local.self_insns)
916 limit = to->local.self_insns;
918 limit = what->local.self_insns;
920 limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
922 newsize = cgraph_estimate_size_after_inlining (times, to, what);
923 if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
926 *reason = N_("--param large-function-growth limit reached");
929 for (i = 0; i < ninlined; i++)
932 cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined[i]) *
933 times, inlined[i], what);
934 if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
936 inlined[i]->local.self_insns *
937 (100 + PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH)) / 100)
939 *reason = N_("--param large-function-growth limit reached while inlining the caller");
946 /* Return true when function N is small enough to be inlined. */
949 cgraph_default_inline_p (struct cgraph_node *n)
951 if (!DECL_INLINE (n->decl) || !DECL_SAVED_TREE (n->decl))
953 if (DECL_DECLARED_INLINE_P (n->decl))
954 return n->global.insns < MAX_INLINE_INSNS_SINGLE;
956 return n->global.insns < MAX_INLINE_INSNS_AUTO;
959 /* Set inline_failed for all callers of given function to REASON. */
962 cgraph_set_inline_failed (struct cgraph_node *node, const char *reason)
964 struct cgraph_edge *e;
966 if (cgraph_dump_file)
967 fprintf (cgraph_dump_file, "Inlining failed: %s\n", reason);
968 for (e = node->callers; e; e = e->next_caller)
969 if (e->inline_failed)
970 e->inline_failed = reason;
973 /* We use greedy algorithm for inlining of small functions:
974 All inline candidates are put into prioritized heap based on estimated
975 growth of the overall number of instructions and then update the estimates.
977 INLINED and INLINED_CALEES are just pointers to arrays large enough
978 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
981 cgraph_decide_inlining_of_small_functions (struct cgraph_node **inlined,
982 struct cgraph_node **inlined_callees)
985 struct cgraph_node *node;
986 fibheap_t heap = fibheap_new ();
987 struct fibnode **heap_node =
988 xcalloc (cgraph_max_uid, sizeof (struct fibnode *));
989 int ninlined, ninlined_callees;
990 int max_insns = ((HOST_WIDEST_INT) initial_insns
991 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
993 /* Put all inline candidates into the heap. */
995 for (node = cgraph_nodes; node; node = node->next)
997 if (!node->local.inlinable || !node->callers
998 || node->local.disregard_inline_limits)
1001 if (!cgraph_default_inline_p (node))
1003 cgraph_set_inline_failed (node,
1004 N_("--param max-inline-insns-single limit reached"));
1007 heap_node[node->uid] =
1008 fibheap_insert (heap, cgraph_estimate_growth (node), node);
1011 if (cgraph_dump_file)
1012 fprintf (cgraph_dump_file, "\nDeciding on smaller functions:\n");
1013 while (overall_insns <= max_insns && (node = fibheap_extract_min (heap)))
1015 struct cgraph_edge *e;
1016 int old_insns = overall_insns;
1018 heap_node[node->uid] = NULL;
1019 if (cgraph_dump_file)
1020 fprintf (cgraph_dump_file,
1021 "\nConsidering %s with %i insns\n"
1022 " Estimated growth is %+i insns.\n",
1023 cgraph_node_name (node), node->global.insns,
1024 cgraph_estimate_growth (node));
1025 if (!cgraph_default_inline_p (node))
1027 cgraph_set_inline_failed (node,
1028 N_("--param max-inline-insns-single limit reached after inlining into the callee"));
1031 ninlined_callees = cgraph_inlined_callees (node, inlined_callees);
1032 for (e = node->callers; e; e = e->next_caller)
1033 if (e->inline_failed)
1035 /* Marking recursive function inlinine has sane semantic and
1036 thus we should not warn on it. */
1037 if (e->caller == node)
1039 e->inline_failed = "";
1042 ninlined = cgraph_inlined_into (e->caller, inlined);
1043 if (e->callee->output)
1044 e->inline_failed = "";
1045 if (e->callee->output
1046 || !cgraph_check_inline_limits (e->caller, node, inlined,
1047 ninlined, &e->inline_failed))
1049 for (i = 0; i < ninlined; i++)
1050 inlined[i]->output = 0, node->aux = 0;
1051 if (cgraph_dump_file)
1052 fprintf (cgraph_dump_file, " Not inlining into %s.\n",
1053 cgraph_node_name (e->caller));
1056 cgraph_mark_inline (e->caller, node, inlined, ninlined,
1057 inlined_callees, ninlined_callees);
1058 if (heap_node[e->caller->uid])
1059 fibheap_replace_key (heap, heap_node[e->caller->uid],
1060 cgraph_estimate_growth (e->caller));
1062 /* Size of the functions we updated into has changed, so update
1064 for (i = 0; i < ninlined; i++)
1066 inlined[i]->output = 0, node->aux = 0;
1067 if (heap_node[inlined[i]->uid])
1068 fibheap_replace_key (heap, heap_node[inlined[i]->uid],
1069 cgraph_estimate_growth (inlined[i]));
1071 if (cgraph_dump_file)
1072 fprintf (cgraph_dump_file,
1073 " Inlined into %s which now has %i insns.\n",
1074 cgraph_node_name (e->caller),
1075 e->caller->global.insns);
1079 /* Similarly all functions called by the function we just inlined
1080 are now called more times; update keys. */
1082 for (e = node->callees; e; e = e->next_callee)
1083 if (e->inline_failed && heap_node[e->callee->uid])
1084 fibheap_replace_key (heap, heap_node[e->callee->uid],
1085 cgraph_estimate_growth (e->callee));
1087 for (i = 0; i < ninlined_callees; i++)
1089 struct cgraph_edge *e;
1091 for (e = inlined_callees[i]->callees; e; e = e->next_callee)
1092 if (e->inline_failed && heap_node[e->callee->uid])
1093 fibheap_replace_key (heap, heap_node[e->callee->uid],
1094 cgraph_estimate_growth (e->callee));
1096 inlined_callees[i]->output = 0, node->aux = 0;
1098 if (cgraph_dump_file)
1099 fprintf (cgraph_dump_file,
1100 " Inlined %i times for a net change of %+i insns.\n",
1101 node->global.cloned_times, overall_insns - old_insns);
1103 while ((node = fibheap_extract_min (heap)) != NULL)
1104 if (!node->local.disregard_inline_limits)
1105 cgraph_set_inline_failed (node, N_("--param inline-unit-growth limit reached"));
1106 fibheap_delete (heap);
1110 /* Decide on the inlining. We do so in the topological order to avoid
1111 expenses on updating datastructures. */
1114 cgraph_decide_inlining (void)
1116 struct cgraph_node *node;
1118 struct cgraph_node **order =
1119 xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1120 struct cgraph_node **inlined =
1121 xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1122 struct cgraph_node **inlined_callees =
1123 xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1125 int ninlined_callees;
1129 for (node = cgraph_nodes; node; node = node->next)
1130 initial_insns += node->local.self_insns;
1131 overall_insns = initial_insns;
1133 nnodes = cgraph_postorder (order);
1135 if (cgraph_dump_file)
1136 fprintf (cgraph_dump_file,
1137 "\nDeciding on inlining. Starting with %i insns.\n",
1140 for (node = cgraph_nodes; node; node = node->next)
1143 if (cgraph_dump_file)
1144 fprintf (cgraph_dump_file, "\nInlining always_inline functions:\n");
1146 /* In the first pass mark all always_inline edges. Do this with a priority
1147 so none of our later choices will make this impossible. */
1148 for (i = nnodes - 1; i >= 0; i--)
1150 struct cgraph_edge *e;
1154 for (e = node->callees; e; e = e->next_callee)
1155 if (e->callee->local.disregard_inline_limits)
1159 if (cgraph_dump_file)
1160 fprintf (cgraph_dump_file,
1161 "\nConsidering %s %i insns (always inline)\n",
1162 cgraph_node_name (e->callee), e->callee->global.insns);
1163 ninlined = cgraph_inlined_into (order[i], inlined);
1164 for (; e; e = e->next_callee)
1166 old_insns = overall_insns;
1167 if (!e->inline_failed || !e->callee->local.inlinable
1168 || !e->callee->local.disregard_inline_limits)
1170 if (e->callee->output || e->callee == node)
1172 e->inline_failed = N_("recursive inlining");
1176 cgraph_inlined_callees (e->callee, inlined_callees);
1177 cgraph_mark_inline (node, e->callee, inlined, ninlined,
1178 inlined_callees, ninlined_callees);
1179 for (y = 0; y < ninlined_callees; y++)
1180 inlined_callees[y]->output = 0, node->aux = 0;
1181 if (cgraph_dump_file)
1182 fprintf (cgraph_dump_file,
1183 " Inlined into %s which now has %i insns.\n",
1184 cgraph_node_name (node->callees->caller),
1185 node->callees->caller->global.insns);
1187 if (cgraph_dump_file && node->global.cloned_times > 0)
1188 fprintf (cgraph_dump_file,
1189 " Inlined %i times for a net change of %+i insns.\n",
1190 node->global.cloned_times, overall_insns - old_insns);
1191 for (y = 0; y < ninlined; y++)
1192 inlined[y]->output = 0, node->aux = 0;
1195 if (!flag_really_no_inline)
1197 cgraph_decide_inlining_of_small_functions (inlined, inlined_callees);
1199 if (cgraph_dump_file)
1200 fprintf (cgraph_dump_file, "\nDeciding on functions called once:\n");
1202 /* And finally decide what functions are called once. */
1204 for (i = nnodes - 1; i >= 0; i--)
1208 if (node->callers && !node->callers->next_caller && !node->needed
1209 && node->local.inlinable && node->callers->inline_failed
1210 && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
1213 struct cgraph_node *node1;
1215 /* Verify that we won't duplicate the caller. */
1216 for (node1 = node->callers->caller;
1217 node1->callers && !node1->callers->inline_failed
1218 && ok; node1 = node1->callers->caller)
1219 if (node1->callers->next_caller || node1->needed)
1223 const char *dummy_reason;
1224 if (cgraph_dump_file)
1225 fprintf (cgraph_dump_file,
1226 "\nConsidering %s %i insns.\n"
1227 " Called once from %s %i insns.\n",
1228 cgraph_node_name (node), node->global.insns,
1229 cgraph_node_name (node->callers->caller),
1230 node->callers->caller->global.insns);
1231 ninlined = cgraph_inlined_into (node->callers->caller,
1233 old_insns = overall_insns;
1235 /* Inlining functions once would never cause inlining warnings. */
1236 if (cgraph_check_inline_limits
1237 (node->callers->caller, node, inlined, ninlined,
1241 cgraph_inlined_callees (node, inlined_callees);
1242 cgraph_mark_inline (node->callers->caller, node, inlined,
1243 ninlined, inlined_callees,
1245 for (y = 0; y < ninlined_callees; y++)
1246 inlined_callees[y]->output = 0, node->aux = 0;
1247 if (cgraph_dump_file)
1248 fprintf (cgraph_dump_file,
1249 " Inlined into %s which now has %i insns"
1250 " for a net change of %+i insns.\n",
1251 cgraph_node_name (node->callers->caller),
1252 node->callers->caller->global.insns,
1253 overall_insns - old_insns);
1257 if (cgraph_dump_file)
1258 fprintf (cgraph_dump_file,
1259 " Inline limit reached, not inlined.\n");
1261 for (y = 0; y < ninlined; y++)
1262 inlined[y]->output = 0, node->aux = 0;
1268 if (cgraph_dump_file)
1269 fprintf (cgraph_dump_file,
1270 "\nInlined %i calls, eliminated %i functions, "
1271 "%i insns turned to %i insns.\n\n",
1272 ncalls_inlined, nfunctions_inlined, initial_insns,
1276 free (inlined_callees);
1279 /* Decide on the inlining. We do so in the topological order to avoid
1280 expenses on updating datastructures. */
1283 cgraph_decide_inlining_incrementally (struct cgraph_node *node)
1285 struct cgraph_edge *e;
1286 struct cgraph_node **inlined =
1287 xmalloc (sizeof (struct cgraph_node *) * cgraph_n_nodes);
1288 struct cgraph_node **inlined_callees =
1289 xmalloc (sizeof (struct cgraph_node *) * cgraph_n_nodes);
1291 int ninlined_callees;
1294 ninlined = cgraph_inlined_into (node, inlined);
1296 /* First of all look for always inline functions. */
1297 for (e = node->callees; e; e = e->next_callee)
1298 if (e->callee->local.disregard_inline_limits && e->inline_failed
1299 /* ??? It is possible that renaming variable removed the function body
1300 in duplicate_decls. See gcc.c-torture/compile/20011119-2.c */
1301 && DECL_SAVED_TREE (e->callee->decl))
1303 if (e->callee->output || e->callee == node)
1305 e->inline_failed = N_("recursive inlining");
1308 ninlined_callees = cgraph_inlined_callees (e->callee, inlined_callees);
1309 cgraph_mark_inline (node, e->callee, inlined, ninlined,
1310 inlined_callees, ninlined_callees);
1311 for (y = 0; y < ninlined_callees; y++)
1312 inlined_callees[y]->output = 0, node->aux = 0;
1315 if (!flag_really_no_inline)
1317 /* Now do the automatic inlining. */
1318 for (e = node->callees; e; e = e->next_callee)
1319 if (e->callee->local.inlinable && e->inline_failed
1320 && cgraph_default_inline_p (e->callee)
1321 && cgraph_check_inline_limits (node, e->callee, inlined,
1322 ninlined, &e->inline_failed)
1323 && DECL_SAVED_TREE (e->callee->decl))
1325 /* Marking recursive function inlinine has sane semantic and thus
1326 we should not warn on it. */
1327 if (e->callee->output || e->callee == node)
1329 e->inline_failed = "";
1332 ninlined_callees = cgraph_inlined_callees (e->callee,
1334 cgraph_mark_inline (node, e->callee, inlined, ninlined,
1335 inlined_callees, ninlined_callees);
1336 for (y = 0; y < ninlined_callees; y++)
1337 inlined_callees[y]->output = 0, node->aux = 0;
1341 /* Clear the flags set by cgraph_inlined_into. */
1342 for (y = 0; y < ninlined; y++)
1343 inlined[y]->output = 0, node->aux = 0;
1346 free (inlined_callees);
1350 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL.
1351 When returned false and reason is non-NULL, set it to the reason
1352 why the call was not inlined. */
1355 cgraph_inline_p (tree caller_decl, tree callee_decl, const char **reason)
1357 struct cgraph_node *caller = cgraph_node (caller_decl);
1358 struct cgraph_node *callee = cgraph_node (callee_decl);
1359 struct cgraph_edge *e;
1361 for (e = caller->callees; e; e = e->next_callee)
1362 if (e->callee == callee)
1364 if (e->inline_failed && reason)
1365 *reason = e->inline_failed;
1366 return !e->inline_failed;
1368 /* We do not record builtins in the callgraph. Perhaps it would make more
1369 sense to do so and then prune out those not overwritten by explicit
1372 *reason = "originally indirect function calls never inlined";
1375 /* Expand all functions that must be output.
1377 Attempt to topologically sort the nodes so function is output when
1378 all called functions are already assembled to allow data to be
1379 propagated across the callgraph. Use a stack to get smaller distance
1380 between a function and it's callees (later we may choose to use a more
1381 sophisticated algorithm for function reordering; we will likely want
1382 to use subsections to make the output functions appear in top-down
1386 cgraph_expand_all_functions (void)
1388 struct cgraph_node *node;
1389 struct cgraph_node **order =
1390 xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1394 cgraph_mark_functions_to_output ();
1396 order_pos = cgraph_postorder (order);
1398 for (i = order_pos - 1; i >= 0; i--)
1403 if (!node->reachable)
1406 cgraph_expand_function (node);
1412 /* Mark all local functions.
1414 A local function is one whose calls can occur only in the
1415 current compilation unit and all it's calls are explicit,
1416 so we can change its calling convention.
1417 We simply mark all static functions whose address is not taken
1421 cgraph_mark_local_functions (void)
1423 struct cgraph_node *node;
1425 if (cgraph_dump_file)
1426 fprintf (cgraph_dump_file, "\nMarking local functions:");
1428 /* Figure out functions we want to assemble. */
1429 for (node = cgraph_nodes; node; node = node->next)
1431 node->local.local = (!node->needed
1432 && DECL_SAVED_TREE (node->decl)
1433 && !TREE_PUBLIC (node->decl));
1434 if (cgraph_dump_file && node->local.local)
1435 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1437 if (cgraph_dump_file)
1438 fprintf (cgraph_dump_file, "\n\n");
1441 /* Perform simple optimizations based on callgraph. */
1444 cgraph_optimize (void)
1446 if (!flag_unit_at_a_time)
1448 timevar_push (TV_CGRAPHOPT);
1450 fprintf (stderr, "Performing intraprocedural optimizations\n");
1452 cgraph_mark_local_functions ();
1453 if (cgraph_dump_file)
1455 fprintf (cgraph_dump_file, "Marked ");
1456 dump_cgraph (cgraph_dump_file);
1459 cgraph_decide_inlining ();
1460 cgraph_global_info_ready = true;
1461 if (cgraph_dump_file)
1463 fprintf (cgraph_dump_file, "Optimized ");
1464 dump_cgraph (cgraph_dump_file);
1466 timevar_pop (TV_CGRAPHOPT);
1468 /* Output everything. */
1470 fprintf (stderr, "Assembling functions:\n");
1471 cgraph_expand_all_functions ();
1472 if (cgraph_dump_file)
1474 fprintf (cgraph_dump_file, "\nFinal ");
1475 dump_cgraph (cgraph_dump_file);