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"
30 /* Fill array order with all nodes with output flag set in the reverse
34 cgraph_postorder (struct cgraph_node
**order
)
36 struct cgraph_node
*node
, *node2
;
39 struct cgraph_edge
*edge
, last
;
41 struct cgraph_node
**stack
=
42 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
44 /* We have to deal with cycles nicely, so use a depth first traversal
45 output algorithm. Ignore the fact that some functions won't need
46 to be output and put them into order as well, so we get dependencies
47 right through inline functions. */
48 for (node
= cgraph_nodes
; node
; node
= node
->next
)
50 for (node
= cgraph_nodes
; node
; node
= node
->next
)
57 node
->aux
= node
->callers
;
60 while (node2
->aux
!= &last
)
62 edge
= (struct cgraph_edge
*) node2
->aux
;
63 if (edge
->next_caller
)
64 node2
->aux
= edge
->next_caller
;
67 if (!edge
->caller
->aux
)
69 if (!edge
->caller
->callers
)
70 edge
->caller
->aux
= &last
;
72 edge
->caller
->aux
= edge
->caller
->callers
;
73 stack
[stack_size
++] = node2
;
78 if (node2
->aux
== &last
)
80 order
[order_pos
++] = node2
;
82 node2
= stack
[--stack_size
];
89 for (node
= cgraph_nodes
; node
; node
= node
->next
)
94 /* Perform reachability analysis and reclaim all unreachable nodes.
95 If BEFORE_INLINING_P is true this function is called before inlining
96 decisions has been made. If BEFORE_INLINING_P is false this function also
97 removes unneeded bodies of extern inline functions. */
100 cgraph_remove_unreachable_nodes (bool before_inlining_p
, FILE *file
)
102 struct cgraph_node
*first
= (struct cgraph_node
*) (void *) 1;
103 struct cgraph_node
*node
, *next
;
104 bool changed
= false;
106 #ifdef ENABLE_CHECKING
110 fprintf (file
, "\nReclaiming functions:");
111 #ifdef ENABLE_CHECKING
112 for (node
= cgraph_nodes
; node
; node
= node
->next
)
113 gcc_assert (!node
->aux
);
115 for (node
= cgraph_nodes
; node
; node
= node
->next
)
116 if (node
->needed
&& !node
->global
.inlined_to
117 && ((!DECL_EXTERNAL (node
->decl
))
119 || before_inlining_p
))
125 gcc_assert (!node
->aux
);
127 /* Perform reachability analysis. As a special case do not consider
128 extern inline functions not inlined as live because we won't output
130 while (first
!= (void *) 1)
132 struct cgraph_edge
*e
;
134 first
= (struct cgraph_node
*) first
->aux
;
136 for (e
= node
->callees
; e
; e
= e
->next_callee
)
139 && (!e
->inline_failed
|| !e
->callee
->analyzed
140 || (!DECL_EXTERNAL (e
->callee
->decl
))
141 || before_inlining_p
))
143 e
->callee
->aux
= first
;
148 /* Remove unreachable nodes. Extern inline functions need special care;
149 Unreachable extern inline functions shall be removed.
150 Reachable extern inline functions we never inlined shall get their bodies
152 Reachable extern inline functions we sometimes inlined will be turned into
153 unanalyzed nodes so they look like for true extern functions to the rest
154 of code. Body of such functions is released via remove_node once the
155 inline clones are eliminated. */
156 for (node
= cgraph_nodes
; node
; node
= next
)
161 node
->global
.inlined_to
= NULL
;
163 fprintf (file
, " %s", cgraph_node_name (node
));
164 if (!node
->analyzed
|| !DECL_EXTERNAL (node
->decl
)
165 || before_inlining_p
)
166 cgraph_remove_node (node
);
169 struct cgraph_edge
*e
;
171 for (e
= node
->callers
; e
; e
= e
->next_caller
)
174 if (e
|| node
->needed
)
176 struct cgraph_node
*clone
;
178 for (clone
= node
->next_clone
; clone
;
179 clone
= clone
->next_clone
)
184 cgraph_release_function_body (node
);
185 node
->analyzed
= false;
187 cgraph_node_remove_callees (node
);
188 node
->analyzed
= false;
189 node
->local
.inlinable
= false;
192 cgraph_remove_node (node
);
197 for (node
= cgraph_nodes
; node
; node
= node
->next
)
199 #ifdef ENABLE_CHECKING
205 /* Mark visibility of all functions.
207 A local function is one whose calls can occur only in the current
208 compilation unit and all its calls are explicit, so we can change
209 its calling convention. We simply mark all static functions whose
210 address is not taken as local.
212 We also change the TREE_PUBLIC flag of all declarations that are public
213 in language point of view but we want to overwrite this default
214 via visibilities for the backend point of view. */
217 function_and_variable_visibility (void)
219 struct cgraph_node
*node
;
220 struct varpool_node
*vnode
;
222 for (node
= cgraph_nodes
; node
; node
= node
->next
)
225 && (DECL_COMDAT (node
->decl
)
226 || (!flag_whole_program
227 && TREE_PUBLIC (node
->decl
) && !DECL_EXTERNAL (node
->decl
))))
228 node
->local
.externally_visible
= true;
229 if (!node
->local
.externally_visible
&& node
->analyzed
230 && !DECL_EXTERNAL (node
->decl
))
232 gcc_assert (flag_whole_program
|| !TREE_PUBLIC (node
->decl
));
233 TREE_PUBLIC (node
->decl
) = 0;
235 node
->local
.local
= (!node
->needed
237 && !DECL_EXTERNAL (node
->decl
)
238 && !node
->local
.externally_visible
);
240 for (vnode
= varpool_nodes_queue
; vnode
; vnode
= vnode
->next_needed
)
243 && !flag_whole_program
244 && (DECL_COMDAT (vnode
->decl
) || TREE_PUBLIC (vnode
->decl
)))
245 vnode
->externally_visible
= 1;
246 if (!vnode
->externally_visible
)
248 gcc_assert (flag_whole_program
|| !TREE_PUBLIC (vnode
->decl
));
249 TREE_PUBLIC (vnode
->decl
) = 0;
251 gcc_assert (TREE_STATIC (vnode
->decl
));
256 fprintf (dump_file
, "\nMarking local functions:");
257 for (node
= cgraph_nodes
; node
; node
= node
->next
)
258 if (node
->local
.local
)
259 fprintf (dump_file
, " %s", cgraph_node_name (node
));
260 fprintf (dump_file
, "\n\n");
261 fprintf (dump_file
, "\nMarking externally visible functions:");
262 for (node
= cgraph_nodes
; node
; node
= node
->next
)
263 if (node
->local
.externally_visible
)
264 fprintf (dump_file
, " %s", cgraph_node_name (node
));
265 fprintf (dump_file
, "\n\n");
267 cgraph_function_flags_ready
= true;
271 struct simple_ipa_opt_pass pass_ipa_function_and_variable_visibility
=
275 "visibility", /* name */
277 function_and_variable_visibility
, /* execute */
280 0, /* static_pass_number */
281 TV_CGRAPHOPT
, /* tv_id */
282 0, /* properties_required */
283 0, /* properties_provided */
284 0, /* properties_destroyed */
285 0, /* todo_flags_start */
286 TODO_remove_functions
| TODO_dump_cgraph
/* todo_flags_finish */
291 /* Hash a cgraph node set element. */
294 hash_cgraph_node_set_element (const void *p
)
296 const_cgraph_node_set_element element
= (const_cgraph_node_set_element
) p
;
297 return htab_hash_pointer (element
->node
);
300 /* Compare two cgraph node set elements. */
303 eq_cgraph_node_set_element (const void *p1
, const void *p2
)
305 const_cgraph_node_set_element e1
= (const_cgraph_node_set_element
) p1
;
306 const_cgraph_node_set_element e2
= (const_cgraph_node_set_element
) p2
;
308 return e1
->node
== e2
->node
;
311 /* Create a new cgraph node set. */
314 cgraph_node_set_new (void)
316 cgraph_node_set new_node_set
;
318 new_node_set
= GGC_NEW (struct cgraph_node_set_def
);
319 new_node_set
->hashtab
= htab_create_ggc (10,
320 hash_cgraph_node_set_element
,
321 eq_cgraph_node_set_element
,
323 new_node_set
->nodes
= NULL
;
327 /* Add cgraph_node NODE to cgraph_node_set SET. */
330 cgraph_node_set_add (cgraph_node_set set
, struct cgraph_node
*node
)
333 cgraph_node_set_element element
;
334 struct cgraph_node_set_element_def dummy
;
337 slot
= htab_find_slot (set
->hashtab
, &dummy
, INSERT
);
339 if (*slot
!= HTAB_EMPTY_ENTRY
)
341 element
= (cgraph_node_set_element
) *slot
;
342 gcc_assert (node
== element
->node
343 && (VEC_index (cgraph_node_ptr
, set
->nodes
, element
->index
)
348 /* Insert node into hash table. */
350 (cgraph_node_set_element
) GGC_NEW (struct cgraph_node_set_element_def
);
351 element
->node
= node
;
352 element
->index
= VEC_length (cgraph_node_ptr
, set
->nodes
);
355 /* Insert into node vector. */
356 VEC_safe_push (cgraph_node_ptr
, gc
, set
->nodes
, node
);
359 /* Remove cgraph_node NODE from cgraph_node_set SET. */
362 cgraph_node_set_remove (cgraph_node_set set
, struct cgraph_node
*node
)
364 void **slot
, **last_slot
;
365 cgraph_node_set_element element
, last_element
;
366 struct cgraph_node
*last_node
;
367 struct cgraph_node_set_element_def dummy
;
370 slot
= htab_find_slot (set
->hashtab
, &dummy
, NO_INSERT
);
374 element
= (cgraph_node_set_element
) *slot
;
375 gcc_assert (VEC_index (cgraph_node_ptr
, set
->nodes
, element
->index
)
378 /* Remove from vector. We do this by swapping node with the last element
380 last_node
= VEC_pop (cgraph_node_ptr
, set
->nodes
);
381 if (last_node
!= node
)
383 dummy
.node
= last_node
;
384 last_slot
= htab_find_slot (set
->hashtab
, &dummy
, NO_INSERT
);
385 last_element
= (cgraph_node_set_element
) *last_slot
;
386 gcc_assert (last_element
);
388 /* Move the last element to the original spot of NODE. */
389 last_element
->index
= element
->index
;
390 VEC_replace (cgraph_node_ptr
, set
->nodes
, last_element
->index
,
394 /* Remove element from hash table. */
395 htab_clear_slot (set
->hashtab
, slot
);
399 /* Find NODE in SET and return an iterator to it if found. A null iterator
400 is returned if NODE is not in SET. */
402 cgraph_node_set_iterator
403 cgraph_node_set_find (cgraph_node_set set
, struct cgraph_node
*node
)
406 struct cgraph_node_set_element_def dummy
;
407 cgraph_node_set_element element
;
408 cgraph_node_set_iterator csi
;
411 slot
= htab_find_slot (set
->hashtab
, &dummy
, NO_INSERT
);
413 csi
.index
= (unsigned) ~0;
416 element
= (cgraph_node_set_element
) *slot
;
417 gcc_assert (VEC_index (cgraph_node_ptr
, set
->nodes
, element
->index
)
419 csi
.index
= element
->index
;
426 /* Dump content of SET to file F. */
429 dump_cgraph_node_set (FILE *f
, cgraph_node_set set
)
431 cgraph_node_set_iterator iter
;
433 for (iter
= csi_start (set
); !csi_end_p (iter
); csi_next (&iter
))
435 struct cgraph_node
*node
= csi_node (iter
);
436 dump_cgraph_node (f
, node
);
440 /* Dump content of SET to stderr. */
443 debug_cgraph_node_set (cgraph_node_set set
)
445 dump_cgraph_node_set (stderr
, set
);