1 /* Basic IPA optimizations and utilities.
2 Copyright (C) 2003, 2004, 2005, 2007, 2008 Free Software Foundation,
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 3, 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 COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
26 #include "tree-pass.h"
31 /* Fill array order with all nodes with output flag set in the reverse
35 cgraph_postorder (struct cgraph_node
**order
)
37 struct cgraph_node
*node
, *node2
;
40 struct cgraph_edge
*edge
, last
;
43 struct cgraph_node
**stack
=
44 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
46 /* We have to deal with cycles nicely, so use a depth first traversal
47 output algorithm. Ignore the fact that some functions won't need
48 to be output and put them into order as well, so we get dependencies
49 right through inline functions. */
50 for (node
= cgraph_nodes
; node
; node
= node
->next
)
52 for (pass
= 0; pass
< 2; pass
++)
53 for (node
= cgraph_nodes
; node
; node
= node
->next
)
55 && (pass
|| (node
->needed
&& !node
->address_taken
)))
61 node
->aux
= node
->callers
;
64 while (node2
->aux
!= &last
)
66 edge
= (struct cgraph_edge
*) node2
->aux
;
67 if (edge
->next_caller
)
68 node2
->aux
= edge
->next_caller
;
71 if (!edge
->caller
->aux
)
73 if (!edge
->caller
->callers
)
74 edge
->caller
->aux
= &last
;
76 edge
->caller
->aux
= edge
->caller
->callers
;
77 stack
[stack_size
++] = node2
;
82 if (node2
->aux
== &last
)
84 order
[order_pos
++] = node2
;
86 node2
= stack
[--stack_size
];
93 for (node
= cgraph_nodes
; node
; node
= node
->next
)
98 /* Look for all functions inlined to NODE and update their inlined_to pointers
102 update_inlined_to_pointer (struct cgraph_node
*node
, struct cgraph_node
*inlined_to
)
104 struct cgraph_edge
*e
;
105 for (e
= node
->callees
; e
; e
= e
->next_callee
)
106 if (e
->callee
->global
.inlined_to
)
108 e
->callee
->global
.inlined_to
= inlined_to
;
109 update_inlined_to_pointer (e
->callee
, inlined_to
);
113 /* Perform reachability analysis and reclaim all unreachable nodes.
114 If BEFORE_INLINING_P is true this function is called before inlining
115 decisions has been made. If BEFORE_INLINING_P is false this function also
116 removes unneeded bodies of extern inline functions. */
119 cgraph_remove_unreachable_nodes (bool before_inlining_p
, FILE *file
)
121 struct cgraph_node
*first
= (struct cgraph_node
*) (void *) 1;
122 struct cgraph_node
*node
, *next
;
123 bool changed
= false;
125 #ifdef ENABLE_CHECKING
129 fprintf (file
, "\nReclaiming functions:");
130 #ifdef ENABLE_CHECKING
131 for (node
= cgraph_nodes
; node
; node
= node
->next
)
132 gcc_assert (!node
->aux
);
134 for (node
= cgraph_nodes
; node
; node
= node
->next
)
135 if (node
->needed
&& !node
->global
.inlined_to
136 && ((!DECL_EXTERNAL (node
->decl
))
138 || before_inlining_p
))
144 gcc_assert (!node
->aux
);
146 /* Perform reachability analysis. As a special case do not consider
147 extern inline functions not inlined as live because we won't output
149 while (first
!= (void *) 1)
151 struct cgraph_edge
*e
;
153 first
= (struct cgraph_node
*) first
->aux
;
155 for (e
= node
->callees
; e
; e
= e
->next_callee
)
158 && (!e
->inline_failed
|| !e
->callee
->analyzed
159 || (!DECL_EXTERNAL (e
->callee
->decl
))
160 || before_inlining_p
))
162 e
->callee
->aux
= first
;
165 while (node
->clone_of
&& !node
->clone_of
->aux
&& !gimple_has_body_p (node
->decl
))
167 node
= node
->clone_of
;
173 /* Remove unreachable nodes. Extern inline functions need special care;
174 Unreachable extern inline functions shall be removed.
175 Reachable extern inline functions we never inlined shall get their bodies
177 Reachable extern inline functions we sometimes inlined will be turned into
178 unanalyzed nodes so they look like for true extern functions to the rest
179 of code. Body of such functions is released via remove_node once the
180 inline clones are eliminated. */
181 for (node
= cgraph_nodes
; node
; node
= next
)
186 node
->global
.inlined_to
= NULL
;
188 fprintf (file
, " %s", cgraph_node_name (node
));
189 if (!node
->analyzed
|| !DECL_EXTERNAL (node
->decl
)
190 || before_inlining_p
)
191 cgraph_remove_node (node
);
194 struct cgraph_edge
*e
;
196 /* See if there is reachable caller. */
197 for (e
= node
->callers
; e
; e
= e
->next_caller
)
201 /* If so, we need to keep node in the callgraph. */
202 if (e
|| node
->needed
)
204 struct cgraph_node
*clone
;
206 /* If there are still clones, we must keep body around.
207 Otherwise we can just remove the body but keep the clone. */
208 for (clone
= node
->clones
; clone
;
209 clone
= clone
->next_sibling_clone
)
214 cgraph_release_function_body (node
);
215 cgraph_node_remove_callees (node
);
216 node
->analyzed
= false;
217 node
->local
.inlinable
= false;
221 cgraph_remove_node (node
);
226 for (node
= cgraph_nodes
; node
; node
= node
->next
)
228 /* Inline clones might be kept around so their materializing allows further
229 cloning. If the function the clone is inlined into is removed, we need
230 to turn it into normal cone. */
231 if (node
->global
.inlined_to
234 gcc_assert (node
->clones
);
235 node
->global
.inlined_to
= NULL
;
236 update_inlined_to_pointer (node
, node
);
240 #ifdef ENABLE_CHECKING
246 /* Mark visibility of all functions.
248 A local function is one whose calls can occur only in the current
249 compilation unit and all its calls are explicit, so we can change
250 its calling convention. We simply mark all static functions whose
251 address is not taken as local.
253 We also change the TREE_PUBLIC flag of all declarations that are public
254 in language point of view but we want to overwrite this default
255 via visibilities for the backend point of view. */
258 function_and_variable_visibility (void)
260 struct cgraph_node
*node
;
261 struct varpool_node
*vnode
;
263 for (node
= cgraph_nodes
; node
; node
= node
->next
)
266 && (DECL_COMDAT (node
->decl
)
267 || (!flag_whole_program
268 && TREE_PUBLIC (node
->decl
) && !DECL_EXTERNAL (node
->decl
))))
269 node
->local
.externally_visible
= true;
270 if (!node
->local
.externally_visible
&& node
->analyzed
271 && !DECL_EXTERNAL (node
->decl
))
273 gcc_assert (flag_whole_program
|| !TREE_PUBLIC (node
->decl
));
274 TREE_PUBLIC (node
->decl
) = 0;
276 node
->local
.local
= (!node
->needed
278 && !DECL_EXTERNAL (node
->decl
)
279 && !node
->local
.externally_visible
);
281 for (vnode
= varpool_nodes_queue
; vnode
; vnode
= vnode
->next_needed
)
284 && !flag_whole_program
285 && (DECL_COMDAT (vnode
->decl
) || TREE_PUBLIC (vnode
->decl
)))
286 vnode
->externally_visible
= 1;
287 if (!vnode
->externally_visible
)
289 gcc_assert (flag_whole_program
|| !TREE_PUBLIC (vnode
->decl
));
290 TREE_PUBLIC (vnode
->decl
) = 0;
292 gcc_assert (TREE_STATIC (vnode
->decl
));
297 fprintf (dump_file
, "\nMarking local functions:");
298 for (node
= cgraph_nodes
; node
; node
= node
->next
)
299 if (node
->local
.local
)
300 fprintf (dump_file
, " %s", cgraph_node_name (node
));
301 fprintf (dump_file
, "\n\n");
302 fprintf (dump_file
, "\nMarking externally visible functions:");
303 for (node
= cgraph_nodes
; node
; node
= node
->next
)
304 if (node
->local
.externally_visible
)
305 fprintf (dump_file
, " %s", cgraph_node_name (node
));
306 fprintf (dump_file
, "\n\n");
308 cgraph_function_flags_ready
= true;
312 struct simple_ipa_opt_pass pass_ipa_function_and_variable_visibility
=
316 "visibility", /* name */
318 function_and_variable_visibility
, /* execute */
321 0, /* static_pass_number */
322 TV_CGRAPHOPT
, /* tv_id */
323 0, /* properties_required */
324 0, /* properties_provided */
325 0, /* properties_destroyed */
326 0, /* todo_flags_start */
327 TODO_remove_functions
| TODO_dump_cgraph
/* todo_flags_finish */
332 /* Hash a cgraph node set element. */
335 hash_cgraph_node_set_element (const void *p
)
337 const_cgraph_node_set_element element
= (const_cgraph_node_set_element
) p
;
338 return htab_hash_pointer (element
->node
);
341 /* Compare two cgraph node set elements. */
344 eq_cgraph_node_set_element (const void *p1
, const void *p2
)
346 const_cgraph_node_set_element e1
= (const_cgraph_node_set_element
) p1
;
347 const_cgraph_node_set_element e2
= (const_cgraph_node_set_element
) p2
;
349 return e1
->node
== e2
->node
;
352 /* Create a new cgraph node set. */
355 cgraph_node_set_new (void)
357 cgraph_node_set new_node_set
;
359 new_node_set
= GGC_NEW (struct cgraph_node_set_def
);
360 new_node_set
->hashtab
= htab_create_ggc (10,
361 hash_cgraph_node_set_element
,
362 eq_cgraph_node_set_element
,
364 new_node_set
->nodes
= NULL
;
368 /* Add cgraph_node NODE to cgraph_node_set SET. */
371 cgraph_node_set_add (cgraph_node_set set
, struct cgraph_node
*node
)
374 cgraph_node_set_element element
;
375 struct cgraph_node_set_element_def dummy
;
378 slot
= htab_find_slot (set
->hashtab
, &dummy
, INSERT
);
380 if (*slot
!= HTAB_EMPTY_ENTRY
)
382 element
= (cgraph_node_set_element
) *slot
;
383 gcc_assert (node
== element
->node
384 && (VEC_index (cgraph_node_ptr
, set
->nodes
, element
->index
)
389 /* Insert node into hash table. */
391 (cgraph_node_set_element
) GGC_NEW (struct cgraph_node_set_element_def
);
392 element
->node
= node
;
393 element
->index
= VEC_length (cgraph_node_ptr
, set
->nodes
);
396 /* Insert into node vector. */
397 VEC_safe_push (cgraph_node_ptr
, gc
, set
->nodes
, node
);
400 /* Remove cgraph_node NODE from cgraph_node_set SET. */
403 cgraph_node_set_remove (cgraph_node_set set
, struct cgraph_node
*node
)
405 void **slot
, **last_slot
;
406 cgraph_node_set_element element
, last_element
;
407 struct cgraph_node
*last_node
;
408 struct cgraph_node_set_element_def dummy
;
411 slot
= htab_find_slot (set
->hashtab
, &dummy
, NO_INSERT
);
415 element
= (cgraph_node_set_element
) *slot
;
416 gcc_assert (VEC_index (cgraph_node_ptr
, set
->nodes
, element
->index
)
419 /* Remove from vector. We do this by swapping node with the last element
421 last_node
= VEC_pop (cgraph_node_ptr
, set
->nodes
);
422 if (last_node
!= node
)
424 dummy
.node
= last_node
;
425 last_slot
= htab_find_slot (set
->hashtab
, &dummy
, NO_INSERT
);
426 last_element
= (cgraph_node_set_element
) *last_slot
;
427 gcc_assert (last_element
);
429 /* Move the last element to the original spot of NODE. */
430 last_element
->index
= element
->index
;
431 VEC_replace (cgraph_node_ptr
, set
->nodes
, last_element
->index
,
435 /* Remove element from hash table. */
436 htab_clear_slot (set
->hashtab
, slot
);
440 /* Find NODE in SET and return an iterator to it if found. A null iterator
441 is returned if NODE is not in SET. */
443 cgraph_node_set_iterator
444 cgraph_node_set_find (cgraph_node_set set
, struct cgraph_node
*node
)
447 struct cgraph_node_set_element_def dummy
;
448 cgraph_node_set_element element
;
449 cgraph_node_set_iterator csi
;
452 slot
= htab_find_slot (set
->hashtab
, &dummy
, NO_INSERT
);
454 csi
.index
= (unsigned) ~0;
457 element
= (cgraph_node_set_element
) *slot
;
458 gcc_assert (VEC_index (cgraph_node_ptr
, set
->nodes
, element
->index
)
460 csi
.index
= element
->index
;
467 /* Dump content of SET to file F. */
470 dump_cgraph_node_set (FILE *f
, cgraph_node_set set
)
472 cgraph_node_set_iterator iter
;
474 for (iter
= csi_start (set
); !csi_end_p (iter
); csi_next (&iter
))
476 struct cgraph_node
*node
= csi_node (iter
);
477 dump_cgraph_node (f
, node
);
481 /* Dump content of SET to stderr. */
484 debug_cgraph_node_set (cgraph_node_set set
)
486 dump_cgraph_node_set (stderr
, set
);