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"
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);
52 static void cgraph_decide_inlining_incrementally (struct cgraph_node *);
54 /* Statistics we collect about inlining algorithm. */
55 static int ncalls_inlined;
56 static int nfunctions_inlined;
57 static int initial_insns;
58 static int overall_insns;
60 /* Records tree nodes seen in cgraph_create_edges. Simply using
61 walk_tree_without_duplicates doesn't guarantee each node is visited
62 once because it gets a new htab upon each recursive call from
64 static htab_t visited_nodes;
66 /* Determine if function DECL is needed. That is, visible to something
67 either outside this translation unit, something magic in the system
68 configury, or (if not doing unit-at-a-time) to something we havn't
72 decide_is_function_needed (struct cgraph_node *node, tree decl)
74 /* If we decided it was needed before, but at the time we didn't have
75 the body of the function available, then it's still needed. We have
76 to go back and re-check its dependencies now. */
80 /* Externally visible functions must be output. The exception is
81 COMDAT functions that must be output only when they are needed. */
82 if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
85 /* Constructors and destructors are reachable from the runtime by
87 if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl))
90 /* If the user told us it is used, then it must be so. */
91 if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
94 /* ??? If the assembler name is set by hand, it is possible to assemble
95 the name later after finalizing the function and the fact is noticed
96 in assemble_name then. This is arguably a bug. */
97 if (DECL_ASSEMBLER_NAME_SET_P (decl)
98 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
101 if (flag_unit_at_a_time)
104 /* If not doing unit at a time, then we'll only defer this function
105 if its marked for inlining. Otherwise we want to emit it now. */
107 /* "extern inline" functions are never output locally. */
108 if (DECL_EXTERNAL (decl))
110 /* We want to emit COMDAT functions only when absolutely necessary. */
111 if (DECL_COMDAT (decl))
113 if (!DECL_INLINE (decl)
114 || (!node->local.disregard_inline_limits
115 /* When declared inline, defer even the uninlinable functions.
116 This allows them to be eliminated when unused. */
117 && !DECL_DECLARED_INLINE_P (decl)
118 && (!node->local.inlinable || !cgraph_default_inline_p (node))))
124 /* When not doing unit-at-a-time, output all functions enqueued.
125 Return true when such a functions were found. */
128 cgraph_assemble_pending_functions (void)
132 if (flag_unit_at_a_time)
135 while (cgraph_nodes_queue)
137 struct cgraph_node *n = cgraph_nodes_queue;
139 cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
140 if (!n->origin && !DECL_EXTERNAL (n->decl))
142 cgraph_expand_function (n);
150 /* DECL has been parsed. Take it, queue it, compile it at the whim of the
151 logic in effect. If NESTED is true, then our caller cannot stand to have
152 the garbage collector run at the moment. We would need to either create
153 a new GC context, or just not compile right now. */
156 cgraph_finalize_function (tree decl, bool nested)
158 struct cgraph_node *node = cgraph_node (decl);
160 if (node->local.finalized)
162 /* As an GCC extension we allow redefinition of the function. The
163 semantics when both copies of bodies differ is not well defined.
164 We replace the old body with new body so in unit at a time mode
165 we always use new body, while in normal mode we may end up with
166 old body inlined into some functions and new body expanded and
169 ??? It may make more sense to use one body for inlining and other
170 body for expanding the function but this is difficult to do. */
172 /* If node->output is set, then this is a unit-at-a-time compilation
173 and we have already begun whole-unit analysis. This is *not*
174 testing for whether we've already emitted the function. That
175 case can be sort-of legitimately seen with real function
176 redefinition errors. I would argue that the front end should
177 never present us with such a case, but don't enforce that for now. */
181 /* Reset our datastructures so we can analyze the function again. */
182 memset (&node->local, 0, sizeof (node->local));
183 memset (&node->global, 0, sizeof (node->global));
184 memset (&node->rtl, 0, sizeof (node->rtl));
185 node->analyzed = false;
186 while (node->callees)
187 cgraph_remove_edge (node, node->callees->callee);
189 /* We may need to re-queue the node for assembling in case
190 we already proceeded it and ignored as not needed. */
191 if (node->reachable && !flag_unit_at_a_time)
193 struct cgraph_node *n;
195 for (n = cgraph_nodes_queue; n; n = n->next_needed)
203 notice_global_symbol (decl);
205 node->local.finalized = true;
207 /* If not unit at a time, then we need to create the call graph
208 now, so that called functions can be queued and emitted now. */
209 if (!flag_unit_at_a_time)
211 cgraph_analyze_function (node);
212 cgraph_decide_inlining_incrementally (node);
215 if (decide_is_function_needed (node, decl))
216 cgraph_mark_needed_node (node);
218 /* If not unit at a time, go ahead and emit everything we've found
219 to be reachable at this time. */
221 cgraph_assemble_pending_functions ();
223 /* If we've not yet emitted decl, tell the debug info about it. */
224 if (!TREE_ASM_WRITTEN (decl))
225 (*debug_hooks->deferred_inline_function) (decl);
228 /* Walk tree and record all calls. Called via walk_tree. */
230 record_call_1 (tree *tp, int *walk_subtrees, void *data)
234 switch (TREE_CODE (t))
237 /* ??? Really, we should mark this decl as *potentially* referenced
238 by this function and re-examine whether the decl is actually used
239 after rtl has been generated. */
241 cgraph_varpool_mark_needed_node (cgraph_varpool_node (t));
245 if (flag_unit_at_a_time)
247 /* Record dereferences to the functions. This makes the
248 functions reachable unconditionally. */
249 tree decl = TREE_OPERAND (*tp, 0);
250 if (TREE_CODE (decl) == FUNCTION_DECL)
251 cgraph_mark_needed_node (cgraph_node (decl));
257 tree decl = get_callee_fndecl (*tp);
258 if (decl && TREE_CODE (decl) == FUNCTION_DECL)
260 if (DECL_BUILT_IN (decl))
262 cgraph_record_call (data, decl);
264 /* When we see a function call, we don't want to look at the
265 function reference in the ADDR_EXPR that is hanging from
266 the CALL_EXPR we're examining here, because we would
267 conclude incorrectly that the function's address could be
268 taken by something that is not a function call. So only
269 walk the function parameter list, skip the other subtrees. */
271 walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data,
279 /* Save some cycles by not walking types and declaration as we
280 won't find anything useful there anyway. */
281 if (DECL_P (*tp) || TYPE_P (*tp))
287 if ((unsigned int) TREE_CODE (t) >= LAST_AND_UNUSED_TREE_CODE)
288 return (*lang_hooks.callgraph.analyze_expr) (tp, walk_subtrees, data);
295 /* Create cgraph edges for function calls inside BODY from DECL. */
298 cgraph_create_edges (tree decl, tree body)
300 /* The nodes we're interested in are never shared, so walk
301 the tree ignoring duplicates. */
302 visited_nodes = htab_create (37, htab_hash_pointer,
303 htab_eq_pointer, NULL);
304 walk_tree (&body, record_call_1, decl, visited_nodes);
305 htab_delete (visited_nodes);
306 visited_nodes = NULL;
309 /* Analyze the function scheduled to be output. */
311 cgraph_analyze_function (struct cgraph_node *node)
313 tree decl = node->decl;
315 current_function_decl = decl;
317 /* First kill forward declaration so reverse inlining works properly. */
318 cgraph_create_edges (decl, DECL_SAVED_TREE (decl));
320 node->local.inlinable = tree_inlinable_function_p (decl);
321 if (!DECL_ESTIMATED_INSNS (decl))
322 DECL_ESTIMATED_INSNS (decl)
323 = (*lang_hooks.tree_inlining.estimate_num_insns) (decl);
324 node->local.self_insns = DECL_ESTIMATED_INSNS (decl);
325 if (node->local.inlinable)
326 node->local.disregard_inline_limits
327 = (*lang_hooks.tree_inlining.disregard_inline_limits) (decl);
328 if (flag_really_no_inline && !node->local.disregard_inline_limits)
329 node->local.inlinable = 0;
330 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
331 node->global.insns = node->local.self_insns;
332 if (!DECL_EXTERNAL (decl))
334 node->global.cloned_times = 1;
335 node->global.will_be_output = true;
338 node->analyzed = true;
339 current_function_decl = NULL;
342 /* Analyze the whole compilation unit once it is parsed completely. */
345 cgraph_finalize_compilation_unit (void)
347 struct cgraph_node *node;
349 if (!flag_unit_at_a_time)
351 cgraph_assemble_pending_functions ();
355 cgraph_varpool_assemble_pending_decls ();
357 fprintf (stderr, "\nAnalyzing compilation unit\n");
359 timevar_push (TV_CGRAPH);
360 if (cgraph_dump_file)
362 fprintf (cgraph_dump_file, "Initial entry points:");
363 for (node = cgraph_nodes; node; node = node->next)
364 if (node->needed && DECL_SAVED_TREE (node->decl))
365 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
366 fprintf (cgraph_dump_file, "\n");
369 /* Propagate reachability flag and lower representation of all reachable
370 functions. In the future, lowering will introduce new functions and
371 new entry points on the way (by template instantiation and virtual
372 method table generation for instance). */
373 while (cgraph_nodes_queue)
375 struct cgraph_edge *edge;
376 tree decl = cgraph_nodes_queue->decl;
378 node = cgraph_nodes_queue;
379 cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
381 /* ??? It is possible to create extern inline function and later using
382 weak alas attribute to kill it's body. See
383 gcc.c-torture/compile/20011119-1.c */
384 if (!DECL_SAVED_TREE (decl))
387 if (node->analyzed || !node->reachable || !DECL_SAVED_TREE (decl))
390 cgraph_analyze_function (node);
392 for (edge = node->callees; edge; edge = edge->next_callee)
393 if (!edge->callee->reachable)
394 cgraph_mark_reachable_node (edge->callee);
396 cgraph_varpool_assemble_pending_decls ();
399 /* Collect entry points to the unit. */
401 if (cgraph_dump_file)
403 fprintf (cgraph_dump_file, "Unit entry points:");
404 for (node = cgraph_nodes; node; node = node->next)
405 if (node->needed && DECL_SAVED_TREE (node->decl))
406 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
407 fprintf (cgraph_dump_file, "\n\nInitial ");
408 dump_cgraph (cgraph_dump_file);
411 if (cgraph_dump_file)
412 fprintf (cgraph_dump_file, "\nReclaiming functions:");
414 for (node = cgraph_nodes; node; node = node->next)
416 tree decl = node->decl;
418 if (!node->reachable && DECL_SAVED_TREE (decl))
420 cgraph_remove_node (node);
421 if (cgraph_dump_file)
422 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
425 if (cgraph_dump_file)
427 fprintf (cgraph_dump_file, "\n\nReclaimed ");
428 dump_cgraph (cgraph_dump_file);
431 timevar_pop (TV_CGRAPH);
434 /* Figure out what functions we want to assemble. */
437 cgraph_mark_functions_to_output (void)
439 struct cgraph_node *node;
441 for (node = cgraph_nodes; node; node = node->next)
443 tree decl = node->decl;
444 struct cgraph_edge *e;
448 for (e = node->callers; e; e = e->next_caller)
452 /* We need to output all local functions that are used and not
453 always inlined, as well as those that are reachable from
454 outside the current compilation unit. */
455 if (DECL_SAVED_TREE (decl)
457 || (e && node->reachable))
458 && !TREE_ASM_WRITTEN (decl) && !node->origin
459 && !DECL_EXTERNAL (decl))
464 /* Optimize the function before expansion. */
467 cgraph_optimize_function (struct cgraph_node *node)
469 tree decl = node->decl;
471 timevar_push (TV_INTEGRATION);
472 /* optimize_inline_calls avoids inlining of current_function_decl. */
473 current_function_decl = decl;
474 if (flag_inline_trees)
476 struct cgraph_edge *e;
478 for (e = node->callees; e; e = e->next_callee)
479 if (e->inline_call || warn_inline)
482 optimize_inline_calls (decl);
486 for (node = node->nested; node; node = node->next_nested)
487 cgraph_optimize_function (node);
489 timevar_pop (TV_INTEGRATION);
492 /* Expand function specified by NODE. */
495 cgraph_expand_function (struct cgraph_node *node)
497 tree decl = node->decl;
499 if (flag_unit_at_a_time)
500 announce_function (decl);
502 cgraph_optimize_function (node);
504 /* Generate RTL for the body of DECL. Nested functions are expanded
505 via lang_expand_decl_stmt. */
506 (*lang_hooks.callgraph.expand_function) (decl);
508 if (!cgraph_function_possibly_inlined_p (decl))
509 DECL_SAVED_TREE (decl) = NULL;
510 current_function_decl = NULL;
513 /* Fill array order with all nodes with output flag set in the reverse
514 topological order. */
516 cgraph_postorder (struct cgraph_node **order)
518 struct cgraph_node *node, *node2;
521 struct cgraph_edge *edge, last;
523 struct cgraph_node **stack =
524 xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
526 /* We have to deal with cycles nicely, so use a depth first traversal
527 output algorithm. Ignore the fact that some functions won't need
528 to be output and put them into order as well, so we get dependencies
529 right through intline functions. */
530 for (node = cgraph_nodes; node; node = node->next)
532 for (node = cgraph_nodes; node; node = node->next)
539 node->aux = node->callers;
542 while (node2->aux != &last)
545 if (edge->next_caller)
546 node2->aux = edge->next_caller;
549 if (!edge->caller->aux)
551 if (!edge->caller->callers)
552 edge->caller->aux = &last;
554 edge->caller->aux = edge->caller->callers;
555 stack[stack_size++] = node2;
556 node2 = edge->caller;
560 if (node2->aux == &last)
562 order[order_pos++] = node2;
564 node2 = stack[--stack_size];
574 #define INLINED_TIMES(node) ((size_t)(node)->aux)
575 #define SET_INLINED_TIMES(node,times) ((node)->aux = (void *)(times))
577 /* Return list of nodes we decided to inline NODE into, set their output
578 flag and compute INLINED_TIMES.
580 We do simple backtracing to get INLINED_TIMES right. This should not be
581 expensive as we limit the amount of inlining. Alternatively we may first
582 discover set of nodes, topologically sort these and propagate
586 cgraph_inlined_into (struct cgraph_node *node, struct cgraph_node **array)
589 struct cgraph_edge **stack;
590 struct cgraph_edge *e, *e1;
594 /* Fast path: since we traverse in mostly topological order, we will likely
596 for (e = node->callers; e; e = e->next_caller)
603 /* Allocate stack for back-tracking up callgraph. */
604 stack = xmalloc ((cgraph_n_nodes + 1) * sizeof (struct cgraph_edge));
607 /* Push the first edge on to the stack. */
612 struct cgraph_node *caller;
614 /* Look at the edge on the top of the stack. */
618 /* Check if the caller destination has been visited yet. */
621 array[nfound++] = e->caller;
622 /* Mark that we have visited the destination. */
623 caller->output = true;
624 SET_INLINED_TIMES (caller, 0);
626 SET_INLINED_TIMES (caller, INLINED_TIMES (caller) + 1);
628 for (e1 = caller->callers; e1; e1 = e1->next_caller)
637 for (e1 = e->next_caller; e1; e1 = e1->next_caller)
660 if (cgraph_dump_file)
662 fprintf (cgraph_dump_file, " Found inline predecesors of %s:",
663 cgraph_node_name (node));
664 for (i = 0; i < nfound; i++)
666 fprintf (cgraph_dump_file, " %s", cgraph_node_name (array[i]));
667 if (INLINED_TIMES (array[i]) != 1)
668 fprintf (cgraph_dump_file, " (%i times)",
669 (int)INLINED_TIMES (array[i]));
671 fprintf (cgraph_dump_file, "\n");
677 /* Return list of nodes we decided to inline into NODE, set their output
678 flag and compute INLINED_TIMES.
680 This function is identical to cgraph_inlined_into with callers and callees
684 cgraph_inlined_callees (struct cgraph_node *node, struct cgraph_node **array)
687 struct cgraph_edge **stack;
688 struct cgraph_edge *e, *e1;
692 /* Fast path: since we traverse in mostly topological order, we will likely
694 for (e = node->callees; e; e = e->next_callee)
701 /* Allocate stack for back-tracking up callgraph. */
702 stack = xmalloc ((cgraph_n_nodes + 1) * sizeof (struct cgraph_edge));
705 /* Push the first edge on to the stack. */
710 struct cgraph_node *callee;
712 /* Look at the edge on the top of the stack. */
716 /* Check if the callee destination has been visited yet. */
719 array[nfound++] = e->callee;
720 /* Mark that we have visited the destination. */
721 callee->output = true;
722 SET_INLINED_TIMES (callee, 0);
724 SET_INLINED_TIMES (callee, INLINED_TIMES (callee) + 1);
726 for (e1 = callee->callees; e1; e1 = e1->next_callee)
735 for (e1 = e->next_callee; e1; e1 = e1->next_callee)
757 if (cgraph_dump_file)
759 fprintf (cgraph_dump_file, " Found inline successors of %s:",
760 cgraph_node_name (node));
761 for (i = 0; i < nfound; i++)
763 fprintf (cgraph_dump_file, " %s", cgraph_node_name (array[i]));
764 if (INLINED_TIMES (array[i]) != 1)
765 fprintf (cgraph_dump_file, " (%i times)",
766 (int)INLINED_TIMES (array[i]));
768 fprintf (cgraph_dump_file, "\n");
774 /* Estimate size of the function after inlining WHAT into TO. */
777 cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
778 struct cgraph_node *what)
780 return (what->global.insns - INSNS_PER_CALL) * times + to->global.insns;
783 /* Estimate the growth caused by inlining NODE into all callees. */
786 cgraph_estimate_growth (struct cgraph_node *node)
790 int clones_added = 0;
791 struct cgraph_edge *e;
793 for (e = node->callers; e; e = e->next_caller)
796 growth += ((cgraph_estimate_size_after_inlining (1, e->caller, node)
798 e->caller->global.insns) *e->caller->global.cloned_times);
799 calls_saved += e->caller->global.cloned_times;
800 clones_added += e->caller->global.cloned_times;
803 /* ??? Wrong for self recursive functions or cases where we decide to not
804 inline for different reasons, but it is not big deal as in that case
805 we will keep the body around, but we will also avoid some inlining. */
806 if (!node->needed && !node->origin && !DECL_EXTERNAL (node->decl))
807 growth -= node->global.insns, clones_added--;
815 /* Update insn sizes after inlining WHAT into TO that is already inlined into
816 all nodes in INLINED array. */
819 cgraph_mark_inline (struct cgraph_node *to, struct cgraph_node *what,
820 struct cgraph_node **inlined, int ninlined,
821 struct cgraph_node **inlined_callees,
822 int ninlined_callees)
827 struct cgraph_edge *e;
831 what->global.inlined = 1;
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 && flag_unit_at_a_time
856 && !DECL_EXTERNAL (what->decl))
858 if (!what->global.will_be_output)
861 nfunctions_inlined++;
862 what->global.will_be_output = 0;
863 overall_insns -= what->global.insns;
865 what->global.cloned_times += clones;
866 for (i = 0; i < ninlined; i++)
869 cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined[i]) *
870 times, inlined[i], what);
871 if (inlined[i]->global.will_be_output)
872 overall_insns += new_insns - inlined[i]->global.insns;
873 inlined[i]->global.insns = new_insns;
875 for (i = 0; i < ninlined_callees; i++)
877 inlined_callees[i]->global.cloned_times +=
878 INLINED_TIMES (inlined_callees[i]) * clones;
882 /* Return false when inlining WHAT into TO is not good idea as it would cause
883 too large growth of function bodies. */
886 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
887 struct cgraph_node **inlined, int ninlined)
891 struct cgraph_edge *e;
895 for (e = to->callees; e; e = e->next_callee)
896 if (e->callee == what)
899 /* When inlining large function body called once into small function,
900 take the inlined function as base for limiting the growth. */
901 if (to->local.self_insns > what->local.self_insns)
902 limit = to->local.self_insns;
904 limit = what->local.self_insns;
906 limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
908 newsize = cgraph_estimate_size_after_inlining (times, to, what);
909 if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
912 for (i = 0; i < ninlined; i++)
915 cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined[i]) *
916 times, inlined[i], what);
917 if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
919 inlined[i]->local.self_insns *
920 (100 + PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH)) / 100)
926 /* Return true when function N is small enough to be inlined. */
929 cgraph_default_inline_p (struct cgraph_node *n)
931 if (!DECL_INLINE (n->decl) || !DECL_SAVED_TREE (n->decl))
933 if (DECL_DECLARED_INLINE_P (n->decl))
934 return n->global.insns < MAX_INLINE_INSNS_SINGLE;
936 return n->global.insns < MAX_INLINE_INSNS_AUTO;
939 /* We use greedy algorithm for inlining of small functions:
940 All inline candidates are put into prioritized heap based on estimated
941 growth of the overall number of instructions and then update the estimates.
943 INLINED and INLINED_CALEES are just pointers to arrays large enough
944 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
947 cgraph_decide_inlining_of_small_functions (struct cgraph_node **inlined,
948 struct cgraph_node **inlined_callees)
951 struct cgraph_node *node;
952 fibheap_t heap = fibheap_new ();
953 struct fibnode **heap_node =
954 xcalloc (cgraph_max_uid, sizeof (struct fibnode *));
955 int ninlined, ninlined_callees;
956 int max_insns = ((HOST_WIDEST_INT) initial_insns
957 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
959 /* Put all inline candidates into the heap. */
961 for (node = cgraph_nodes; node; node = node->next)
963 struct cgraph_edge *e;
965 if (!node->local.inlinable || !node->callers
966 || !cgraph_default_inline_p (node))
969 /* Rule out always_inline functions we dealt with earlier. */
970 for (e = node->callers; e; e = e->next_caller)
975 heap_node[node->uid] =
976 fibheap_insert (heap, cgraph_estimate_growth (node), node);
979 if (cgraph_dump_file)
980 fprintf (cgraph_dump_file, "\nDeciding on smaller functions:\n");
981 while ((node = fibheap_extract_min (heap)) && overall_insns <= max_insns)
983 struct cgraph_edge *e;
984 int old_insns = overall_insns;
986 heap_node[node->uid] = NULL;
987 if (cgraph_dump_file)
988 fprintf (cgraph_dump_file,
989 "\nConsidering %s with %i insns\n"
990 " Estimated growth is %+i insns.\n",
991 cgraph_node_name (node), node->global.insns,
992 cgraph_estimate_growth (node));
993 if (!cgraph_default_inline_p (node))
995 if (cgraph_dump_file)
996 fprintf (cgraph_dump_file, " Function too large.\n");
999 ninlined_callees = cgraph_inlined_callees (node, inlined_callees);
1000 for (e = node->callers; e; e = e->next_caller)
1001 if (!e->inline_call && e->caller != node)
1003 ninlined = cgraph_inlined_into (e->caller, inlined);
1004 if (e->callee->output
1005 || !cgraph_check_inline_limits (e->caller, node, inlined,
1008 for (i = 0; i < ninlined; i++)
1009 inlined[i]->output = 0, node->aux = 0;
1010 if (cgraph_dump_file)
1011 fprintf (cgraph_dump_file, " Not inlining into %s.\n",
1012 cgraph_node_name (e->caller));
1015 cgraph_mark_inline (e->caller, node, inlined, ninlined,
1016 inlined_callees, ninlined_callees);
1017 if (heap_node[e->caller->uid])
1018 fibheap_replace_key (heap, heap_node[e->caller->uid],
1019 cgraph_estimate_growth (e->caller));
1021 /* Size of the functions we updated into has changed, so update
1023 for (i = 0; i < ninlined; i++)
1025 inlined[i]->output = 0, node->aux = 0;
1026 if (heap_node[inlined[i]->uid])
1027 fibheap_replace_key (heap, heap_node[inlined[i]->uid],
1028 cgraph_estimate_growth (inlined[i]));
1030 if (cgraph_dump_file)
1031 fprintf (cgraph_dump_file,
1032 " Inlined into %s which now has %i insns.\n",
1033 cgraph_node_name (e->caller),
1034 e->caller->global.insns);
1038 /* Similarly all functions called by the function we just inlined
1039 are now called more times; update keys. */
1041 for (e = node->callees; e; e = e->next_callee)
1042 if (!e->inline_call && heap_node[e->callee->uid])
1043 fibheap_replace_key (heap, heap_node[e->callee->uid],
1044 cgraph_estimate_growth (e->callee));
1046 for (i = 0; i < ninlined_callees; i++)
1048 struct cgraph_edge *e;
1050 for (e = inlined_callees[i]->callees; e; e = e->next_callee)
1051 if (!e->inline_call && heap_node[e->callee->uid])
1052 fibheap_replace_key (heap, heap_node[e->callee->uid],
1053 cgraph_estimate_growth (e->callee));
1055 inlined_callees[i]->output = 0, node->aux = 0;
1057 if (cgraph_dump_file)
1058 fprintf (cgraph_dump_file,
1059 " Inlined %i times for a net change of %+i insns.\n",
1060 node->global.cloned_times, overall_insns - old_insns);
1062 if (cgraph_dump_file && !fibheap_empty (heap))
1063 fprintf (cgraph_dump_file, "\nReached the inline-unit-growth limit.\n");
1064 fibheap_delete (heap);
1068 /* Decide on the inlining. We do so in the topological order to avoid
1069 expenses on updating datastructures. */
1072 cgraph_decide_inlining (void)
1074 struct cgraph_node *node;
1076 struct cgraph_node **order =
1077 xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1078 struct cgraph_node **inlined =
1079 xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1080 struct cgraph_node **inlined_callees =
1081 xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1083 int ninlined_callees;
1087 for (node = cgraph_nodes; node; node = node->next)
1088 initial_insns += node->local.self_insns;
1089 overall_insns = initial_insns;
1091 nnodes = cgraph_postorder (order);
1093 if (cgraph_dump_file)
1094 fprintf (cgraph_dump_file,
1095 "\nDeciding on inlining. Starting with %i insns.\n",
1098 for (node = cgraph_nodes; node; node = node->next)
1101 if (cgraph_dump_file)
1102 fprintf (cgraph_dump_file, "\nInlining always_inline functions:\n");
1104 /* In the first pass mark all always_inline edges. Do this with a priority
1105 so none of our later choices will make this impossible. */
1106 for (i = nnodes - 1; i >= 0; i--)
1108 struct cgraph_edge *e;
1112 for (e = node->callees; e; e = e->next_callee)
1113 if (e->callee->local.disregard_inline_limits)
1117 if (cgraph_dump_file)
1118 fprintf (cgraph_dump_file,
1119 "\nConsidering %s %i insns (always inline)\n",
1120 cgraph_node_name (e->callee), e->callee->global.insns);
1121 ninlined = cgraph_inlined_into (order[i], inlined);
1122 for (; e; e = e->next_callee)
1124 old_insns = overall_insns;
1125 if (e->inline_call || !e->callee->local.disregard_inline_limits)
1127 if (e->callee->output || e->callee == node)
1130 cgraph_inlined_callees (e->callee, inlined_callees);
1131 cgraph_mark_inline (node, e->callee, inlined, ninlined,
1132 inlined_callees, ninlined_callees);
1133 for (y = 0; y < ninlined_callees; y++)
1134 inlined_callees[y]->output = 0, node->aux = 0;
1135 if (cgraph_dump_file)
1136 fprintf (cgraph_dump_file,
1137 " Inlined into %s which now has %i insns.\n",
1138 cgraph_node_name (node->callees->caller),
1139 node->callees->caller->global.insns);
1141 if (cgraph_dump_file && node->global.cloned_times > 0)
1142 fprintf (cgraph_dump_file,
1143 " Inlined %i times for a net change of %+i insns.\n",
1144 node->global.cloned_times, overall_insns - old_insns);
1145 for (y = 0; y < ninlined; y++)
1146 inlined[y]->output = 0, node->aux = 0;
1149 if (!flag_really_no_inline)
1151 cgraph_decide_inlining_of_small_functions (inlined, inlined_callees);
1153 if (cgraph_dump_file)
1154 fprintf (cgraph_dump_file, "\nDeciding on functions called once:\n");
1156 /* And finally decide what functions are called once. */
1158 for (i = nnodes - 1; i >= 0; i--)
1162 if (node->callers && !node->callers->next_caller && !node->needed
1163 && node->local.inlinable && !node->callers->inline_call
1164 && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
1167 struct cgraph_node *node1;
1169 /* Verify that we won't duplicate the caller. */
1170 for (node1 = node->callers->caller;
1171 node1->callers && node1->callers->inline_call
1172 && ok; node1 = node1->callers->caller)
1173 if (node1->callers->next_caller || node1->needed)
1177 if (cgraph_dump_file)
1178 fprintf (cgraph_dump_file,
1179 "\nConsidering %s %i insns.\n"
1180 " Called once from %s %i insns.\n",
1181 cgraph_node_name (node), node->global.insns,
1182 cgraph_node_name (node->callers->caller),
1183 node->callers->caller->global.insns);
1184 ninlined = cgraph_inlined_into (node->callers->caller,
1186 old_insns = overall_insns;
1187 if (cgraph_check_inline_limits
1188 (node->callers->caller, node, inlined, ninlined))
1191 cgraph_inlined_callees (node, inlined_callees);
1192 cgraph_mark_inline (node->callers->caller, node, inlined,
1193 ninlined, inlined_callees,
1195 for (y = 0; y < ninlined_callees; y++)
1196 inlined_callees[y]->output = 0, node->aux = 0;
1197 if (cgraph_dump_file)
1198 fprintf (cgraph_dump_file,
1199 " Inlined into %s which now has %i insns"
1200 " for a net change of %+i insns.\n",
1201 cgraph_node_name (node->callers->caller),
1202 node->callers->caller->global.insns,
1203 overall_insns - old_insns);
1207 if (cgraph_dump_file)
1208 fprintf (cgraph_dump_file,
1209 " Inline limit reached, not inlined.\n");
1211 for (y = 0; y < ninlined; y++)
1212 inlined[y]->output = 0, node->aux = 0;
1218 if (cgraph_dump_file)
1219 fprintf (cgraph_dump_file,
1220 "\nInlined %i calls, eliminated %i functions, "
1221 "%i insns turned to %i insns.\n\n",
1222 ncalls_inlined, nfunctions_inlined, initial_insns,
1226 free (inlined_callees);
1229 /* Decide on the inlining. We do so in the topological order to avoid
1230 expenses on updating datastructures. */
1233 cgraph_decide_inlining_incrementally (struct cgraph_node *node)
1235 struct cgraph_edge *e;
1236 struct cgraph_node **inlined =
1237 xmalloc (sizeof (struct cgraph_node *) * cgraph_n_nodes);
1238 struct cgraph_node **inlined_callees =
1239 xmalloc (sizeof (struct cgraph_node *) * cgraph_n_nodes);
1241 int ninlined_callees;
1244 ninlined = cgraph_inlined_into (node, inlined);
1246 /* First of all look for always inline functions. */
1247 for (e = node->callees; e; e = e->next_callee)
1248 if (e->callee->local.disregard_inline_limits && !e->callee->output
1249 && e->callee != node && !e->inline_call)
1251 ninlined_callees = cgraph_inlined_callees (e->callee, inlined_callees);
1252 cgraph_mark_inline (node, e->callee, inlined, ninlined,
1253 inlined_callees, ninlined_callees);
1254 for (y = 0; y < ninlined_callees; y++)
1255 inlined_callees[y]->output = 0, node->aux = 0;
1258 if (!flag_really_no_inline)
1260 /* Now do the automatic inlining. */
1261 for (e = node->callees; e; e = e->next_callee)
1262 if (e->callee->local.inlinable && !e->callee->output
1263 && e->callee != node && !e->inline_call
1264 && cgraph_default_inline_p (e->callee)
1265 && cgraph_check_inline_limits (node, e->callee, inlined,
1268 ninlined_callees = cgraph_inlined_callees (e->callee,
1270 cgraph_mark_inline (node, e->callee, inlined, ninlined,
1271 inlined_callees, ninlined_callees);
1272 for (y = 0; y < ninlined_callees; y++)
1273 inlined_callees[y]->output = 0, node->aux = 0;
1277 /* Clear the flags set by cgraph_inlined_into. */
1278 for (y = 0; y < ninlined; y++)
1279 inlined[y]->output = 0, node->aux = 0;
1282 free (inlined_callees);
1286 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
1289 cgraph_inline_p (tree caller_decl, tree callee_decl)
1291 struct cgraph_node *caller = cgraph_node (caller_decl);
1292 struct cgraph_node *callee = cgraph_node (callee_decl);
1293 struct cgraph_edge *e;
1295 for (e = caller->callees; e; e = e->next_callee)
1296 if (e->callee == callee)
1297 return e->inline_call;
1298 /* We do not record builtins in the callgraph. Perhaps it would make more
1299 sense to do so and then prune out those not overwritten by explicit
1303 /* Expand all functions that must be output.
1305 Attempt to topologically sort the nodes so function is output when
1306 all called functions are already assembled to allow data to be
1307 propagated across the callgraph. Use a stack to get smaller distance
1308 between a function and it's callees (later we may choose to use a more
1309 sophisticated algorithm for function reordering; we will likely want
1310 to use subsections to make the output functions appear in top-down
1314 cgraph_expand_all_functions (void)
1316 struct cgraph_node *node;
1317 struct cgraph_node **order =
1318 xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1322 cgraph_mark_functions_to_output ();
1324 order_pos = cgraph_postorder (order);
1326 for (i = order_pos - 1; i >= 0; i--)
1331 if (!node->reachable)
1334 cgraph_expand_function (node);
1340 /* Mark all local functions.
1342 A local function is one whose calls can occur only in the
1343 current compilation unit, so we change its calling convention.
1344 We simply mark all static functions whose address is not taken
1348 cgraph_mark_local_functions (void)
1350 struct cgraph_node *node;
1352 if (cgraph_dump_file)
1353 fprintf (cgraph_dump_file, "\nMarking local functions:");
1355 /* Figure out functions we want to assemble. */
1356 for (node = cgraph_nodes; node; node = node->next)
1358 node->local.local = (!node->needed
1359 && DECL_SAVED_TREE (node->decl)
1360 && !TREE_PUBLIC (node->decl));
1361 if (cgraph_dump_file && node->local.local)
1362 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1364 if (cgraph_dump_file)
1365 fprintf (cgraph_dump_file, "\n\n");
1368 /* Perform simple optimizations based on callgraph. */
1371 cgraph_optimize (void)
1373 if (!flag_unit_at_a_time)
1375 timevar_push (TV_CGRAPHOPT);
1377 fprintf (stderr, "Performing intraprocedural optimizations\n");
1379 cgraph_mark_local_functions ();
1380 if (cgraph_dump_file)
1382 fprintf (cgraph_dump_file, "Marked ");
1383 dump_cgraph (cgraph_dump_file);
1386 cgraph_decide_inlining ();
1387 cgraph_global_info_ready = true;
1388 if (cgraph_dump_file)
1390 fprintf (cgraph_dump_file, "Optimized ");
1391 dump_cgraph (cgraph_dump_file);
1393 timevar_pop (TV_CGRAPHOPT);
1395 /* Output everything. */
1397 fprintf (stderr, "Assembling functions:\n");
1398 cgraph_expand_all_functions ();
1399 if (cgraph_dump_file)
1401 fprintf (cgraph_dump_file, "\nFinal ");
1402 dump_cgraph (cgraph_dump_file);