1 /* Callgraph based intraprocedural optimizations.
2 Copyright (C) 2003, 2004, 2005 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
22 /* This module implements main driver of compilation process as well as
23 few basic intraprocedural optimizers.
25 The main scope of this file is to act as an interface in between
26 tree based frontends and the backend (and middle end)
28 The front-end is supposed to use following functionality:
30 - cgraph_finalize_function
32 This function is called once front-end has parsed whole body of function
33 and it is certain that the function body nor the declaration will change.
35 (There is one exception needed for implementing GCC extern inline function.)
37 - cgraph_varpool_finalize_variable
39 This function has same behavior as the above but is used for static
42 - cgraph_finalize_compilation_unit
44 This function is called once compilation unit is finalized and it will
47 In the unit-at-a-time the call-graph construction and local function
48 analysis takes place here. Bodies of unreachable functions are released
49 to conserve memory usage.
51 ??? The compilation unit in this point of view should be compilation
52 unit as defined by the language - for instance C frontend allows multiple
53 compilation units to be parsed at once and it should call function each
54 time parsing is done so we save memory.
58 In this unit-at-a-time compilation the intra procedural analysis takes
59 place here. In particular the static functions whose address is never
60 taken are marked as local. Backend can then use this information to
61 modify calling conventions, do better inlining or similar optimizations.
63 - cgraph_assemble_pending_functions
64 - cgraph_varpool_assemble_pending_variables
66 In non-unit-at-a-time mode these functions can be used to force compilation
67 of functions or variables that are known to be needed at given stage
70 - cgraph_mark_needed_node
71 - cgraph_varpool_mark_needed_node
73 When function or variable is referenced by some hidden way (for instance
74 via assembly code and marked by attribute "used"), the call-graph data structure
75 must be updated accordingly by this function.
77 - analyze_expr callback
79 This function is responsible for lowering tree nodes not understood by
80 generic code into understandable ones or alternatively marking
81 callgraph and varpool nodes referenced by the as needed.
83 ??? On the tree-ssa genericizing should take place here and we will avoid
84 need for these hooks (replacing them by genericizing hook)
86 - expand_function callback
88 This function is used to expand function and pass it into RTL back-end.
89 Front-end should not make any assumptions about when this function can be
90 called. In particular cgraph_assemble_pending_functions,
91 cgraph_varpool_assemble_pending_variables, cgraph_finalize_function,
92 cgraph_varpool_finalize_function, cgraph_optimize can cause arbitrarily
93 previously finalized functions to be expanded.
95 We implement two compilation modes.
97 - unit-at-a-time: In this mode analyzing of all functions is deferred
98 to cgraph_finalize_compilation_unit and expansion into cgraph_optimize.
100 In cgraph_finalize_compilation_unit the reachable functions are
101 analyzed. During analysis the call-graph edges from reachable
102 functions are constructed and their destinations are marked as
103 reachable. References to functions and variables are discovered too
104 and variables found to be needed output to the assembly file. Via
105 mark_referenced call in assemble_variable functions referenced by
106 static variables are noticed too.
108 The intra-procedural information is produced and its existence
109 indicated by global_info_ready. Once this flag is set it is impossible
110 to change function from !reachable to reachable and thus
111 assemble_variable no longer call mark_referenced.
113 Finally the call-graph is topologically sorted and all reachable functions
114 that has not been completely inlined or are not external are output.
116 ??? It is possible that reference to function or variable is optimized
117 out. We can not deal with this nicely because topological order is not
118 suitable for it. For tree-ssa we may consider another pass doing
119 optimization and re-discovering reachable functions.
121 ??? Reorganize code so variables are output very last and only if they
122 really has been referenced by produced code, so we catch more cases
123 where reference has been optimized out.
127 All functions are variables are output as early as possible to conserve
128 memory consumption. This may or may not result in less memory used but
129 it is still needed for some legacy code that rely on particular ordering
130 of things output from the compiler.
132 Varpool data structures are not used and variables are output directly.
134 Functions are output early using call of
135 cgraph_assemble_pending_function from cgraph_finalize_function. The
136 decision on whether function is needed is made more conservative so
137 uninlininable static functions are needed too. During the call-graph
138 construction the edge destinations are not marked as reachable and it
139 is completely relied upn assemble_variable to mark them.
141 Inlining decision heuristics
142 ??? Move this to separate file after tree-ssa merge.
144 We separate inlining decisions from the inliner itself and store it
145 inside callgraph as so called inline plan. Refer to cgraph.c
146 documentation about particular representation of inline plans in the
149 The implementation of particular heuristics is separated from
150 the rest of code to make it easier to replace it with more complicated
151 implementation in the future. The rest of inlining code acts as a
152 library aimed to modify the callgraph and verify that the parameters
153 on code size growth fits.
155 To mark given call inline, use cgraph_mark_inline function, the
156 verification is performed by cgraph_default_inline_p and
157 cgraph_check_inline_limits.
159 The heuristics implements simple knapsack style algorithm ordering
160 all functions by their "profitability" (estimated by code size growth)
161 and inlining them in priority order.
163 cgraph_decide_inlining implements heuristics taking whole callgraph
164 into account, while cgraph_decide_inlining_incrementally considers
165 only one function at a time and is used in non-unit-at-a-time mode. */
170 #include "coretypes.h"
174 #include "tree-flow.h"
175 #include "tree-inline.h"
176 #include "langhooks.h"
177 #include "pointer-set.h"
184 #include "diagnostic.h"
188 #include "c-common.h"
190 #include "function.h"
191 #include "tree-gimple.h"
192 #include "tree-pass.h"
195 static void cgraph_expand_all_functions (void);
196 static void cgraph_mark_functions_to_output (void);
197 static void cgraph_expand_function (struct cgraph_node
*);
198 static tree
record_call_1 (tree
*, int *, void *);
199 static void cgraph_mark_local_functions (void);
200 static void cgraph_analyze_function (struct cgraph_node
*node
);
202 /* Records tree nodes seen in cgraph_create_edges. Simply using
203 walk_tree_without_duplicates doesn't guarantee each node is visited
204 once because it gets a new htab upon each recursive call from
206 static struct pointer_set_t
*visited_nodes
;
208 static FILE *cgraph_dump_file
;
210 /* Determine if function DECL is needed. That is, visible to something
211 either outside this translation unit, something magic in the system
212 configury, or (if not doing unit-at-a-time) to something we havn't
216 decide_is_function_needed (struct cgraph_node
*node
, tree decl
)
220 /* If we decided it was needed before, but at the time we didn't have
221 the body of the function available, then it's still needed. We have
222 to go back and re-check its dependencies now. */
226 /* Externally visible functions must be output. The exception is
227 COMDAT functions that must be output only when they are needed. */
228 if (TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
) && !DECL_EXTERNAL (decl
))
231 /* Constructors and destructors are reachable from the runtime by
233 if (DECL_STATIC_CONSTRUCTOR (decl
) || DECL_STATIC_DESTRUCTOR (decl
))
236 /* If the user told us it is used, then it must be so. */
237 if (lookup_attribute ("used", DECL_ATTRIBUTES (decl
)))
240 /* ??? If the assembler name is set by hand, it is possible to assemble
241 the name later after finalizing the function and the fact is noticed
242 in assemble_name then. This is arguably a bug. */
243 if (DECL_ASSEMBLER_NAME_SET_P (decl
)
244 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
)))
247 if (flag_unit_at_a_time
)
250 /* If not doing unit at a time, then we'll only defer this function
251 if its marked for inlining. Otherwise we want to emit it now. */
253 /* "extern inline" functions are never output locally. */
254 if (DECL_EXTERNAL (decl
))
256 /* Nested functions of extern inline function shall not be emit unless
257 we inlined the origin. */
258 for (origin
= decl_function_context (decl
); origin
;
259 origin
= decl_function_context (origin
))
260 if (DECL_EXTERNAL (origin
))
262 /* We want to emit COMDAT functions only when absolutely necessary. */
263 if (DECL_COMDAT (decl
))
265 if (!DECL_INLINE (decl
)
266 || (!node
->local
.disregard_inline_limits
267 /* When declared inline, defer even the uninlinable functions.
268 This allows them to be eliminated when unused. */
269 && !DECL_DECLARED_INLINE_P (decl
)
270 && (!node
->local
.inlinable
|| !cgraph_default_inline_p (node
))))
276 /* Walk the decls we marked as necessary and see if they reference new
277 variables or functions and add them into the worklists. */
279 cgraph_varpool_analyze_pending_decls (void)
281 bool changed
= false;
282 timevar_push (TV_CGRAPH
);
284 while (cgraph_varpool_first_unanalyzed_node
)
286 tree decl
= cgraph_varpool_first_unanalyzed_node
->decl
;
288 cgraph_varpool_first_unanalyzed_node
->analyzed
= true;
290 cgraph_varpool_first_unanalyzed_node
= cgraph_varpool_first_unanalyzed_node
->next_needed
;
292 if (DECL_INITIAL (decl
))
293 cgraph_create_edges (NULL
, DECL_INITIAL (decl
));
296 timevar_pop (TV_CGRAPH
);
300 /* Optimization of function bodies might've rendered some variables as
301 unnecessary so we want to avoid these from being compiled.
303 This is done by prunning the queue and keeping only the variables that
304 really appear needed (ie they are either externally visible or referenced
305 by compiled function). Re-doing the reachability analysis on variables
306 brings back the remaining variables referenced by these. */
308 cgraph_varpool_remove_unreferenced_decls (void)
310 struct cgraph_varpool_node
*next
, *node
= cgraph_varpool_nodes_queue
;
312 cgraph_varpool_reset_queue ();
314 if (errorcount
|| sorrycount
)
319 tree decl
= node
->decl
;
320 next
= node
->next_needed
;
324 && ((DECL_ASSEMBLER_NAME_SET_P (decl
)
325 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
)))
326 || node
->force_output
327 || decide_is_variable_needed (node
, decl
)))
328 cgraph_varpool_mark_needed_node (node
);
332 cgraph_varpool_analyze_pending_decls ();
336 /* When not doing unit-at-a-time, output all functions enqueued.
337 Return true when such a functions were found. */
340 cgraph_assemble_pending_functions (void)
344 if (flag_unit_at_a_time
)
347 while (cgraph_nodes_queue
)
349 struct cgraph_node
*n
= cgraph_nodes_queue
;
351 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
352 n
->next_needed
= NULL
;
353 if (!n
->global
.inlined_to
355 && !DECL_EXTERNAL (n
->decl
))
357 cgraph_expand_function (n
);
365 /* DECL has been parsed. Take it, queue it, compile it at the whim of the
366 logic in effect. If NESTED is true, then our caller cannot stand to have
367 the garbage collector run at the moment. We would need to either create
368 a new GC context, or just not compile right now. */
371 cgraph_finalize_function (tree decl
, bool nested
)
373 struct cgraph_node
*node
= cgraph_node (decl
);
375 if (node
->local
.finalized
)
377 /* As an GCC extension we allow redefinition of the function. The
378 semantics when both copies of bodies differ is not well defined.
379 We replace the old body with new body so in unit at a time mode
380 we always use new body, while in normal mode we may end up with
381 old body inlined into some functions and new body expanded and
384 ??? It may make more sense to use one body for inlining and other
385 body for expanding the function but this is difficult to do. */
387 /* If node->output is set, then this is a unit-at-a-time compilation
388 and we have already begun whole-unit analysis. This is *not*
389 testing for whether we've already emitted the function. That
390 case can be sort-of legitimately seen with real function
391 redefinition errors. I would argue that the front end should
392 never present us with such a case, but don't enforce that for now. */
393 gcc_assert (!node
->output
);
395 /* Reset our data structures so we can analyze the function again. */
396 memset (&node
->local
, 0, sizeof (node
->local
));
397 memset (&node
->global
, 0, sizeof (node
->global
));
398 memset (&node
->rtl
, 0, sizeof (node
->rtl
));
399 node
->analyzed
= false;
400 node
->local
.redefined_extern_inline
= true;
402 if (!flag_unit_at_a_time
)
404 struct cgraph_node
*n
;
406 for (n
= cgraph_nodes
; n
; n
= n
->next
)
407 if (n
->global
.inlined_to
== node
)
408 cgraph_remove_node (n
);
411 cgraph_node_remove_callees (node
);
413 /* We may need to re-queue the node for assembling in case
414 we already proceeded it and ignored as not needed. */
415 if (node
->reachable
&& !flag_unit_at_a_time
)
417 struct cgraph_node
*n
;
419 for (n
= cgraph_nodes_queue
; n
; n
= n
->next_needed
)
427 notice_global_symbol (decl
);
429 node
->local
.finalized
= true;
430 node
->lowered
= DECL_STRUCT_FUNCTION (decl
)->cfg
!= NULL
;
432 lower_nested_functions (decl
);
433 gcc_assert (!node
->nested
);
435 /* If not unit at a time, then we need to create the call graph
436 now, so that called functions can be queued and emitted now. */
437 if (!flag_unit_at_a_time
)
439 cgraph_analyze_function (node
);
440 cgraph_decide_inlining_incrementally (node
);
443 if (decide_is_function_needed (node
, decl
))
444 cgraph_mark_needed_node (node
);
446 /* If not unit at a time, go ahead and emit everything we've found
447 to be reachable at this time. */
450 if (!cgraph_assemble_pending_functions ())
454 /* If we've not yet emitted decl, tell the debug info about it. */
455 if (!TREE_ASM_WRITTEN (decl
))
456 (*debug_hooks
->deferred_inline_function
) (decl
);
458 /* Possibly warn about unused parameters. */
459 if (warn_unused_parameter
)
460 do_warn_unused_parameter (decl
);
464 cgraph_lower_function (struct cgraph_node
*node
)
468 tree_lowering_passes (node
->decl
);
469 node
->lowered
= true;
473 /* Walk tree and record all calls. Called via walk_tree. */
475 record_call_1 (tree
*tp
, int *walk_subtrees
, void *data
)
479 switch (TREE_CODE (t
))
482 /* ??? Really, we should mark this decl as *potentially* referenced
483 by this function and re-examine whether the decl is actually used
484 after rtl has been generated. */
485 if (TREE_STATIC (t
) || DECL_EXTERNAL (t
))
487 cgraph_varpool_mark_needed_node (cgraph_varpool_node (t
));
488 if (lang_hooks
.callgraph
.analyze_expr
)
489 return lang_hooks
.callgraph
.analyze_expr (tp
, walk_subtrees
,
496 if (flag_unit_at_a_time
)
498 /* Record dereferences to the functions. This makes the
499 functions reachable unconditionally. */
500 tree decl
= TREE_OPERAND (*tp
, 0);
501 if (TREE_CODE (decl
) == FUNCTION_DECL
)
502 cgraph_mark_needed_node (cgraph_node (decl
));
508 tree decl
= get_callee_fndecl (*tp
);
509 if (decl
&& TREE_CODE (decl
) == FUNCTION_DECL
)
511 cgraph_create_edge (data
, cgraph_node (decl
), *tp
);
513 /* When we see a function call, we don't want to look at the
514 function reference in the ADDR_EXPR that is hanging from
515 the CALL_EXPR we're examining here, because we would
516 conclude incorrectly that the function's address could be
517 taken by something that is not a function call. So only
518 walk the function parameter list, skip the other subtrees. */
520 walk_tree (&TREE_OPERAND (*tp
, 1), record_call_1
, data
,
528 /* Save some cycles by not walking types and declaration as we
529 won't find anything useful there anyway. */
530 if (IS_TYPE_OR_DECL_P (*tp
))
536 if ((unsigned int) TREE_CODE (t
) >= LAST_AND_UNUSED_TREE_CODE
)
537 return lang_hooks
.callgraph
.analyze_expr (tp
, walk_subtrees
, data
);
544 /* Create cgraph edges for function calls inside BODY from NODE. */
547 cgraph_create_edges (struct cgraph_node
*node
, tree body
)
549 /* The nodes we're interested in are never shared, so walk
550 the tree ignoring duplicates. */
551 visited_nodes
= pointer_set_create ();
552 if (TREE_CODE (body
) == FUNCTION_DECL
)
554 struct function
*this_cfun
= DECL_STRUCT_FUNCTION (body
);
555 basic_block this_block
;
556 block_stmt_iterator bsi
;
559 /* Reach the trees by walking over the CFG, and note the
560 enclosing basic-blocks in the call edges. */
561 FOR_EACH_BB_FN (this_block
, this_cfun
)
562 for (bsi
= bsi_start (this_block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
563 walk_tree (bsi_stmt_ptr (bsi
), record_call_1
, node
, visited_nodes
);
565 /* Walk over any private statics that may take addresses of functions. */
566 if (TREE_CODE (DECL_INITIAL (body
)) == BLOCK
)
568 for (step
= BLOCK_VARS (DECL_INITIAL (body
));
570 step
= TREE_CHAIN (step
))
571 if (DECL_INITIAL (step
))
572 walk_tree (&DECL_INITIAL (step
), record_call_1
, node
, visited_nodes
);
575 /* Also look here for private statics. */
576 if (DECL_STRUCT_FUNCTION (body
))
577 for (step
= DECL_STRUCT_FUNCTION (body
)->unexpanded_var_list
;
579 step
= TREE_CHAIN (step
))
581 tree decl
= TREE_VALUE (step
);
582 if (DECL_INITIAL (decl
) && TREE_STATIC (decl
))
583 walk_tree (&DECL_INITIAL (decl
), record_call_1
, node
, visited_nodes
);
587 walk_tree (&body
, record_call_1
, node
, visited_nodes
);
589 walk_tree (&body
, record_call_1
, node
, visited_nodes
);
590 pointer_set_destroy (visited_nodes
);
591 visited_nodes
= NULL
;
594 static bool error_found
;
596 /* Callback of verify_cgraph_node. Check that all call_exprs have
600 verify_cgraph_node_1 (tree
*tp
, int *walk_subtrees
, void *data
)
605 if (TREE_CODE (t
) == CALL_EXPR
&& (decl
= get_callee_fndecl (t
)))
607 struct cgraph_edge
*e
= cgraph_edge (data
, t
);
612 error ("Shared call_expr:");
616 if (e
->callee
->decl
!= cgraph_node (decl
)->decl
)
618 error ("Edge points to wrong declaration:");
619 debug_tree (e
->callee
->decl
);
620 fprintf (stderr
," Instead of:");
627 error ("Missing callgraph edge for call expr:");
633 /* Save some cycles by not walking types and declaration as we
634 won't find anything useful there anyway. */
635 if (IS_TYPE_OR_DECL_P (*tp
))
641 /* Verify cgraph nodes of given cgraph node. */
643 verify_cgraph_node (struct cgraph_node
*node
)
645 struct cgraph_edge
*e
;
646 struct cgraph_node
*main_clone
;
647 struct function
*this_cfun
= DECL_STRUCT_FUNCTION (node
->decl
);
648 basic_block this_block
;
649 block_stmt_iterator bsi
;
651 timevar_push (TV_CGRAPH_VERIFY
);
653 for (e
= node
->callees
; e
; e
= e
->next_callee
)
656 error ("Aux field set for edge %s->%s",
657 cgraph_node_name (e
->caller
), cgraph_node_name (e
->callee
));
660 for (e
= node
->callers
; e
; e
= e
->next_caller
)
662 if (!e
->inline_failed
)
664 if (node
->global
.inlined_to
665 != (e
->caller
->global
.inlined_to
666 ? e
->caller
->global
.inlined_to
: e
->caller
))
668 error ("Inlined_to pointer is wrong");
671 if (node
->callers
->next_caller
)
673 error ("Multiple inline callers");
678 if (node
->global
.inlined_to
)
680 error ("Inlined_to pointer set for noninline callers");
684 if (!node
->callers
&& node
->global
.inlined_to
)
686 error ("Inlined_to pointer is set but no predecesors found");
689 if (node
->global
.inlined_to
== node
)
691 error ("Inlined_to pointer reffers to itself");
695 for (main_clone
= cgraph_node (node
->decl
); main_clone
;
696 main_clone
= main_clone
->next_clone
)
697 if (main_clone
== node
)
701 error ("Node not found in DECL_ASSEMBLER_NAME hash");
706 && DECL_SAVED_TREE (node
->decl
) && !TREE_ASM_WRITTEN (node
->decl
)
707 && (!DECL_EXTERNAL (node
->decl
) || node
->global
.inlined_to
))
711 /* The nodes we're interested in are never shared, so walk
712 the tree ignoring duplicates. */
713 visited_nodes
= pointer_set_create ();
714 /* Reach the trees by walking over the CFG, and note the
715 enclosing basic-blocks in the call edges. */
716 FOR_EACH_BB_FN (this_block
, this_cfun
)
717 for (bsi
= bsi_start (this_block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
718 walk_tree (bsi_stmt_ptr (bsi
), verify_cgraph_node_1
, node
, visited_nodes
);
719 pointer_set_destroy (visited_nodes
);
720 visited_nodes
= NULL
;
723 /* No CFG available?! */
726 for (e
= node
->callees
; e
; e
= e
->next_callee
)
730 error ("Edge %s->%s has no corresponding call_expr",
731 cgraph_node_name (e
->caller
),
732 cgraph_node_name (e
->callee
));
740 dump_cgraph_node (stderr
, node
);
741 internal_error ("verify_cgraph_node failed.");
743 timevar_pop (TV_CGRAPH_VERIFY
);
746 /* Verify whole cgraph structure. */
750 struct cgraph_node
*node
;
752 if (sorrycount
|| errorcount
)
755 for (node
= cgraph_nodes
; node
; node
= node
->next
)
756 verify_cgraph_node (node
);
760 /* Output all variables enqueued to be assembled. */
762 cgraph_varpool_assemble_pending_decls (void)
764 bool changed
= false;
766 if (errorcount
|| sorrycount
)
769 /* EH might mark decls as needed during expansion. This should be safe since
770 we don't create references to new function, but it should not be used
772 cgraph_varpool_analyze_pending_decls ();
774 while (cgraph_varpool_nodes_queue
)
776 tree decl
= cgraph_varpool_nodes_queue
->decl
;
777 struct cgraph_varpool_node
*node
= cgraph_varpool_nodes_queue
;
779 cgraph_varpool_nodes_queue
= cgraph_varpool_nodes_queue
->next_needed
;
780 if (!TREE_ASM_WRITTEN (decl
) && !node
->alias
&& !DECL_EXTERNAL (decl
))
782 assemble_variable (decl
, 0, 1, 0);
785 node
->next_needed
= NULL
;
790 /* Analyze the function scheduled to be output. */
792 cgraph_analyze_function (struct cgraph_node
*node
)
794 tree decl
= node
->decl
;
795 struct cgraph_edge
*e
;
797 current_function_decl
= decl
;
798 push_cfun (DECL_STRUCT_FUNCTION (decl
));
799 cgraph_lower_function (node
);
801 /* First kill forward declaration so reverse inlining works properly. */
802 cgraph_create_edges (node
, decl
);
804 node
->local
.inlinable
= tree_inlinable_function_p (decl
);
805 node
->local
.self_insns
= estimate_num_insns (decl
);
806 if (node
->local
.inlinable
)
807 node
->local
.disregard_inline_limits
808 = lang_hooks
.tree_inlining
.disregard_inline_limits (decl
);
809 for (e
= node
->callers
; e
; e
= e
->next_caller
)
811 if (node
->local
.redefined_extern_inline
)
812 e
->inline_failed
= N_("redefined extern inline functions are not "
813 "considered for inlining");
814 else if (!node
->local
.inlinable
)
815 e
->inline_failed
= N_("function not inlinable");
817 e
->inline_failed
= N_("function not considered for inlining");
819 if (flag_really_no_inline
&& !node
->local
.disregard_inline_limits
)
820 node
->local
.inlinable
= 0;
821 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
822 node
->global
.insns
= node
->local
.self_insns
;
824 node
->analyzed
= true;
826 current_function_decl
= NULL
;
829 /* Analyze the whole compilation unit once it is parsed completely. */
832 cgraph_finalize_compilation_unit (void)
834 struct cgraph_node
*node
;
835 /* Keep track of already processed nodes when called multiple times for
836 intermodule optimization. */
837 static struct cgraph_node
*first_analyzed
;
841 if (!flag_unit_at_a_time
)
843 cgraph_assemble_pending_functions ();
849 fprintf (stderr
, "\nAnalyzing compilation unit");
853 timevar_push (TV_CGRAPH
);
854 cgraph_varpool_analyze_pending_decls ();
855 if (cgraph_dump_file
)
857 fprintf (cgraph_dump_file
, "Initial entry points:");
858 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
859 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
860 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
861 fprintf (cgraph_dump_file
, "\n");
864 /* Propagate reachability flag and lower representation of all reachable
865 functions. In the future, lowering will introduce new functions and
866 new entry points on the way (by template instantiation and virtual
867 method table generation for instance). */
868 while (cgraph_nodes_queue
)
870 struct cgraph_edge
*edge
;
871 tree decl
= cgraph_nodes_queue
->decl
;
873 node
= cgraph_nodes_queue
;
874 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
875 node
->next_needed
= NULL
;
877 /* ??? It is possible to create extern inline function and later using
878 weak alias attribute to kill its body. See
879 gcc.c-torture/compile/20011119-1.c */
880 if (!DECL_SAVED_TREE (decl
))
883 gcc_assert (!node
->analyzed
&& node
->reachable
);
884 gcc_assert (DECL_SAVED_TREE (decl
));
886 cgraph_analyze_function (node
);
888 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
889 if (!edge
->callee
->reachable
)
890 cgraph_mark_reachable_node (edge
->callee
);
892 cgraph_varpool_analyze_pending_decls ();
895 /* Collect entry points to the unit. */
897 if (cgraph_dump_file
)
899 fprintf (cgraph_dump_file
, "Unit entry points:");
900 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
901 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
902 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
903 fprintf (cgraph_dump_file
, "\n\nInitial ");
904 dump_cgraph (cgraph_dump_file
);
907 if (cgraph_dump_file
)
908 fprintf (cgraph_dump_file
, "\nReclaiming functions:");
910 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
912 tree decl
= node
->decl
;
914 if (!node
->reachable
&& DECL_SAVED_TREE (decl
))
916 if (cgraph_dump_file
)
917 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
918 cgraph_remove_node (node
);
921 node
->next_needed
= NULL
;
923 if (cgraph_dump_file
)
925 fprintf (cgraph_dump_file
, "\n\nReclaimed ");
926 dump_cgraph (cgraph_dump_file
);
928 first_analyzed
= cgraph_nodes
;
930 timevar_pop (TV_CGRAPH
);
932 /* Figure out what functions we want to assemble. */
935 cgraph_mark_functions_to_output (void)
937 struct cgraph_node
*node
;
939 for (node
= cgraph_nodes
; node
; node
= node
->next
)
941 tree decl
= node
->decl
;
942 struct cgraph_edge
*e
;
944 gcc_assert (!node
->output
);
946 for (e
= node
->callers
; e
; e
= e
->next_caller
)
947 if (e
->inline_failed
)
950 /* We need to output all local functions that are used and not
951 always inlined, as well as those that are reachable from
952 outside the current compilation unit. */
953 if (DECL_SAVED_TREE (decl
)
954 && !node
->global
.inlined_to
956 || (e
&& node
->reachable
))
957 && !TREE_ASM_WRITTEN (decl
)
958 && !DECL_EXTERNAL (decl
))
962 /* We should've reclaimed all functions that are not needed. */
963 #ifdef ENABLE_CHECKING
964 if (!node
->global
.inlined_to
&& DECL_SAVED_TREE (decl
)
965 && !DECL_EXTERNAL (decl
))
967 dump_cgraph_node (stderr
, node
);
968 internal_error ("failed to reclaim unneeded function");
971 gcc_assert (node
->global
.inlined_to
|| !DECL_SAVED_TREE (decl
)
972 || DECL_EXTERNAL (decl
));
979 /* Expand function specified by NODE. */
982 cgraph_expand_function (struct cgraph_node
*node
)
984 tree decl
= node
->decl
;
986 /* We ought to not compile any inline clones. */
987 gcc_assert (!node
->global
.inlined_to
);
989 if (flag_unit_at_a_time
)
990 announce_function (decl
);
992 /* Generate RTL for the body of DECL. */
993 lang_hooks
.callgraph
.expand_function (decl
);
995 /* Make sure that BE didn't give up on compiling. */
996 /* ??? Can happen with nested function of extern inline. */
997 gcc_assert (TREE_ASM_WRITTEN (node
->decl
));
999 current_function_decl
= NULL
;
1000 if (!cgraph_preserve_function_body_p (node
->decl
))
1002 DECL_SAVED_TREE (node
->decl
) = NULL
;
1003 DECL_STRUCT_FUNCTION (node
->decl
) = NULL
;
1004 DECL_INITIAL (node
->decl
) = error_mark_node
;
1005 /* Eliminate all call edges. This is important so the call_expr no longer
1006 points to the dead function body. */
1007 cgraph_node_remove_callees (node
);
1011 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
1014 cgraph_inline_p (struct cgraph_edge
*e
, const char **reason
)
1016 *reason
= e
->inline_failed
;
1017 return !e
->inline_failed
;
1022 /* Expand all functions that must be output.
1024 Attempt to topologically sort the nodes so function is output when
1025 all called functions are already assembled to allow data to be
1026 propagated across the callgraph. Use a stack to get smaller distance
1027 between a function and its callees (later we may choose to use a more
1028 sophisticated algorithm for function reordering; we will likely want
1029 to use subsections to make the output functions appear in top-down
1033 cgraph_expand_all_functions (void)
1035 struct cgraph_node
*node
;
1036 struct cgraph_node
**order
=
1037 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1038 int order_pos
= 0, new_order_pos
= 0;
1041 order_pos
= cgraph_postorder (order
);
1042 gcc_assert (order_pos
== cgraph_n_nodes
);
1044 /* Garbage collector may remove inline clones we eliminate during
1045 optimization. So we must be sure to not reference them. */
1046 for (i
= 0; i
< order_pos
; i
++)
1047 if (order
[i
]->output
)
1048 order
[new_order_pos
++] = order
[i
];
1050 for (i
= new_order_pos
- 1; i
>= 0; i
--)
1055 gcc_assert (node
->reachable
);
1057 cgraph_expand_function (node
);
1063 /* Mark all local functions.
1065 A local function is one whose calls can occur only in the current
1066 compilation unit and all its calls are explicit, so we can change
1067 its calling convention. We simply mark all static functions whose
1068 address is not taken as local. */
1071 cgraph_mark_local_functions (void)
1073 struct cgraph_node
*node
;
1075 /* Figure out functions we want to assemble. */
1076 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1078 node
->local
.local
= (!node
->needed
1079 && DECL_SAVED_TREE (node
->decl
)
1080 && !TREE_PUBLIC (node
->decl
));
1083 if (cgraph_dump_file
)
1085 fprintf (cgraph_dump_file
, "\nMarking local functions:");
1086 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1087 if (node
->local
.local
)
1088 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
1089 fprintf (cgraph_dump_file
, "\n\n");
1093 /* Return true when function body of DECL still needs to be kept around
1094 for later re-use. */
1096 cgraph_preserve_function_body_p (tree decl
)
1098 struct cgraph_node
*node
;
1099 /* Keep the body; we're going to dump it. */
1100 if (dump_enabled_p (TDI_tree_all
))
1102 if (!cgraph_global_info_ready
)
1103 return (DECL_INLINE (decl
) && !flag_really_no_inline
);
1104 /* Look if there is any clone around. */
1105 for (node
= cgraph_node (decl
); node
; node
= node
->next_clone
)
1106 if (node
->global
.inlined_to
)
1111 /* Perform simple optimizations based on callgraph. */
1114 cgraph_optimize (void)
1116 #ifdef ENABLE_CHECKING
1119 if (!flag_unit_at_a_time
)
1121 cgraph_varpool_assemble_pending_decls ();
1125 process_pending_assemble_externals ();
1127 /* Frontend may output common variables after the unit has been finalized.
1128 It is safe to deal with them here as they are always zero initialized. */
1129 cgraph_varpool_analyze_pending_decls ();
1131 timevar_push (TV_CGRAPHOPT
);
1133 fprintf (stderr
, "Performing intraprocedural optimizations\n");
1135 cgraph_mark_local_functions ();
1136 if (cgraph_dump_file
)
1138 fprintf (cgraph_dump_file
, "Marked ");
1139 dump_cgraph (cgraph_dump_file
);
1142 cgraph_global_info_ready
= true;
1143 if (cgraph_dump_file
)
1145 fprintf (cgraph_dump_file
, "Optimized ");
1146 dump_cgraph (cgraph_dump_file
);
1147 dump_varpool (cgraph_dump_file
);
1149 timevar_pop (TV_CGRAPHOPT
);
1151 /* Output everything. */
1153 fprintf (stderr
, "Assembling functions:\n");
1154 #ifdef ENABLE_CHECKING
1158 cgraph_mark_functions_to_output ();
1159 cgraph_expand_all_functions ();
1160 cgraph_varpool_remove_unreferenced_decls ();
1162 cgraph_varpool_assemble_pending_decls ();
1164 if (cgraph_dump_file
)
1166 fprintf (cgraph_dump_file
, "\nFinal ");
1167 dump_cgraph (cgraph_dump_file
);
1169 #ifdef ENABLE_CHECKING
1171 /* Double check that all inline clones are gone and that all
1172 function bodies have been released from memory. */
1173 if (flag_unit_at_a_time
1174 && !dump_enabled_p (TDI_tree_all
)
1175 && !(sorrycount
|| errorcount
))
1177 struct cgraph_node
*node
;
1178 bool error_found
= false;
1180 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1182 && (node
->global
.inlined_to
1183 || DECL_SAVED_TREE (node
->decl
)))
1186 dump_cgraph_node (stderr
, node
);
1189 internal_error ("Nodes with no released memory found.");
1194 /* Generate and emit a static constructor or destructor. WHICH must be
1195 one of 'I' or 'D'. BODY should be a STATEMENT_LIST containing
1196 GENERIC statements. */
1199 cgraph_build_static_cdtor (char which
, tree body
, int priority
)
1201 static int counter
= 0;
1203 tree decl
, name
, resdecl
;
1205 sprintf (which_buf
, "%c_%d", which
, counter
++);
1206 name
= get_file_function_name_long (which_buf
);
1208 decl
= build_decl (FUNCTION_DECL
, name
,
1209 build_function_type (void_type_node
, void_list_node
));
1210 current_function_decl
= decl
;
1212 resdecl
= build_decl (RESULT_DECL
, NULL_TREE
, void_type_node
);
1213 DECL_ARTIFICIAL (resdecl
) = 1;
1214 DECL_IGNORED_P (resdecl
) = 1;
1215 DECL_RESULT (decl
) = resdecl
;
1217 allocate_struct_function (decl
);
1219 TREE_STATIC (decl
) = 1;
1220 TREE_USED (decl
) = 1;
1221 DECL_ARTIFICIAL (decl
) = 1;
1222 DECL_IGNORED_P (decl
) = 1;
1223 DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
) = 1;
1224 DECL_SAVED_TREE (decl
) = body
;
1225 TREE_PUBLIC (decl
) = ! targetm
.have_ctors_dtors
;
1226 DECL_UNINLINABLE (decl
) = 1;
1228 DECL_INITIAL (decl
) = make_node (BLOCK
);
1229 TREE_USED (DECL_INITIAL (decl
)) = 1;
1231 DECL_SOURCE_LOCATION (decl
) = input_location
;
1232 cfun
->function_end_locus
= input_location
;
1237 DECL_STATIC_CONSTRUCTOR (decl
) = 1;
1240 DECL_STATIC_DESTRUCTOR (decl
) = 1;
1246 gimplify_function_tree (decl
);
1248 /* ??? We will get called LATE in the compilation process. */
1249 if (cgraph_global_info_ready
)
1251 tree_lowering_passes (decl
);
1252 tree_rest_of_compilation (decl
);
1255 cgraph_finalize_function (decl
, 0);
1257 if (targetm
.have_ctors_dtors
)
1259 void (*fn
) (rtx
, int);
1262 fn
= targetm
.asm_out
.constructor
;
1264 fn
= targetm
.asm_out
.destructor
;
1265 fn (XEXP (DECL_RTL (decl
), 0), priority
);
1272 cgraph_dump_file
= dump_begin (TDI_cgraph
, NULL
);