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;
42 struct cgraph_node **stack =
43 XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
45 /* We have to deal with cycles nicely, so use a depth first traversal
46 output algorithm. Ignore the fact that some functions won't need
47 to be output and put them into order as well, so we get dependencies
48 right through inline functions. */
49 for (node = cgraph_nodes; node; node = node->next)
51 for (node = cgraph_nodes; node; node = node->next)
58 node->aux = node->callers;
61 while (node2->aux != &last)
63 edge = (struct cgraph_edge *) node2->aux;
64 if (edge->next_caller)
65 node2->aux = edge->next_caller;
68 if (!edge->caller->aux)
70 if (!edge->caller->callers)
71 edge->caller->aux = &last;
73 edge->caller->aux = edge->caller->callers;
74 stack[stack_size++] = node2;
79 if (node2->aux == &last)
81 order[order_pos++] = node2;
83 node2 = stack[--stack_size];
90 for (node = cgraph_nodes; node; node = node->next)
95 /* Perform reachability analysis and reclaim all unreachable nodes.
96 If BEFORE_INLINING_P is true this function is called before inlining
97 decisions has been made. If BEFORE_INLINING_P is false this function also
98 removes unneeded bodies of extern inline functions. */
101 cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file)
103 struct cgraph_node *first = (struct cgraph_node *) (void *) 1;
104 struct cgraph_node *node, *next;
105 bool changed = false;
107 #ifdef ENABLE_CHECKING
111 fprintf (file, "\nReclaiming functions:");
112 #ifdef ENABLE_CHECKING
113 for (node = cgraph_nodes; node; node = node->next)
114 gcc_assert (!node->aux);
116 for (node = cgraph_nodes; node; node = node->next)
117 if (node->needed && !node->global.inlined_to
118 && ((!DECL_EXTERNAL (node->decl))
120 || before_inlining_p))
126 gcc_assert (!node->aux);
128 /* Perform reachability analysis. As a special case do not consider
129 extern inline functions not inlined as live because we won't output
131 while (first != (void *) 1)
133 struct cgraph_edge *e;
135 first = (struct cgraph_node *) first->aux;
137 for (e = node->callees; e; e = e->next_callee)
140 && (!e->inline_failed || !e->callee->analyzed
141 || (!DECL_EXTERNAL (e->callee->decl))
142 || before_inlining_p))
144 e->callee->aux = first;
147 while (node->clone_of && !node->clone_of->aux && !gimple_has_body_p (node->decl))
149 node = node->clone_of;
155 /* Remove unreachable nodes. Extern inline functions need special care;
156 Unreachable extern inline functions shall be removed.
157 Reachable extern inline functions we never inlined shall get their bodies
159 Reachable extern inline functions we sometimes inlined will be turned into
160 unanalyzed nodes so they look like for true extern functions to the rest
161 of code. Body of such functions is released via remove_node once the
162 inline clones are eliminated. */
163 for (node = cgraph_nodes; node; node = next)
168 node->global.inlined_to = NULL;
170 fprintf (file, " %s", cgraph_node_name (node));
171 if (!node->analyzed || !DECL_EXTERNAL (node->decl)
172 || before_inlining_p)
173 cgraph_remove_node (node);
176 struct cgraph_edge *e;
178 /* See if there is reachable caller. */
179 for (e = node->callers; e; e = e->next_caller)
183 /* If so, we need to keep node in the callgraph. */
184 if (e || node->needed)
186 struct cgraph_node *clone;
188 /* If there are still clones, we must keep body around.
189 Otherwise we can just remove the body but keep the clone. */
190 for (clone = node->clones; clone;
191 clone = clone->next_sibling_clone)
196 cgraph_release_function_body (node);
197 cgraph_node_remove_callees (node);
198 node->analyzed = false;
199 node->local.inlinable = false;
203 cgraph_remove_node (node);
208 for (node = cgraph_nodes; node; node = node->next)
210 /* Inline clones might be kept around so their materializing allows further
211 cloning. If the function the clone is inlined into is removed, we need
212 to turn it into normal cone. */
213 if (node->global.inlined_to
216 gcc_assert (node->clones);
217 node->global.inlined_to = false;
221 #ifdef ENABLE_CHECKING
227 /* Mark visibility of all functions.
229 A local function is one whose calls can occur only in the current
230 compilation unit and all its calls are explicit, so we can change
231 its calling convention. We simply mark all static functions whose
232 address is not taken as local.
234 We also change the TREE_PUBLIC flag of all declarations that are public
235 in language point of view but we want to overwrite this default
236 via visibilities for the backend point of view. */
239 function_and_variable_visibility (void)
241 struct cgraph_node *node;
242 struct varpool_node *vnode;
244 for (node = cgraph_nodes; node; node = node->next)
247 && (DECL_COMDAT (node->decl)
248 || (!flag_whole_program
249 && TREE_PUBLIC (node->decl) && !DECL_EXTERNAL (node->decl))))
250 node->local.externally_visible = true;
251 if (!node->local.externally_visible && node->analyzed
252 && !DECL_EXTERNAL (node->decl))
254 gcc_assert (flag_whole_program || !TREE_PUBLIC (node->decl));
255 TREE_PUBLIC (node->decl) = 0;
257 node->local.local = (!node->needed
259 && !DECL_EXTERNAL (node->decl)
260 && !node->local.externally_visible);
262 for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
265 && !flag_whole_program
266 && (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl)))
267 vnode->externally_visible = 1;
268 if (!vnode->externally_visible)
270 gcc_assert (flag_whole_program || !TREE_PUBLIC (vnode->decl));
271 TREE_PUBLIC (vnode->decl) = 0;
273 gcc_assert (TREE_STATIC (vnode->decl));
278 fprintf (dump_file, "\nMarking local functions:");
279 for (node = cgraph_nodes; node; node = node->next)
280 if (node->local.local)
281 fprintf (dump_file, " %s", cgraph_node_name (node));
282 fprintf (dump_file, "\n\n");
283 fprintf (dump_file, "\nMarking externally visible functions:");
284 for (node = cgraph_nodes; node; node = node->next)
285 if (node->local.externally_visible)
286 fprintf (dump_file, " %s", cgraph_node_name (node));
287 fprintf (dump_file, "\n\n");
289 cgraph_function_flags_ready = true;
293 struct simple_ipa_opt_pass pass_ipa_function_and_variable_visibility =
297 "visibility", /* name */
299 function_and_variable_visibility, /* execute */
302 0, /* static_pass_number */
303 TV_CGRAPHOPT, /* tv_id */
304 0, /* properties_required */
305 0, /* properties_provided */
306 0, /* properties_destroyed */
307 0, /* todo_flags_start */
308 TODO_remove_functions | TODO_dump_cgraph/* todo_flags_finish */
313 /* Hash a cgraph node set element. */
316 hash_cgraph_node_set_element (const void *p)
318 const_cgraph_node_set_element element = (const_cgraph_node_set_element) p;
319 return htab_hash_pointer (element->node);
322 /* Compare two cgraph node set elements. */
325 eq_cgraph_node_set_element (const void *p1, const void *p2)
327 const_cgraph_node_set_element e1 = (const_cgraph_node_set_element) p1;
328 const_cgraph_node_set_element e2 = (const_cgraph_node_set_element) p2;
330 return e1->node == e2->node;
333 /* Create a new cgraph node set. */
336 cgraph_node_set_new (void)
338 cgraph_node_set new_node_set;
340 new_node_set = GGC_NEW (struct cgraph_node_set_def);
341 new_node_set->hashtab = htab_create_ggc (10,
342 hash_cgraph_node_set_element,
343 eq_cgraph_node_set_element,
345 new_node_set->nodes = NULL;
349 /* Add cgraph_node NODE to cgraph_node_set SET. */
352 cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
355 cgraph_node_set_element element;
356 struct cgraph_node_set_element_def dummy;
359 slot = htab_find_slot (set->hashtab, &dummy, INSERT);
361 if (*slot != HTAB_EMPTY_ENTRY)
363 element = (cgraph_node_set_element) *slot;
364 gcc_assert (node == element->node
365 && (VEC_index (cgraph_node_ptr, set->nodes, element->index)
370 /* Insert node into hash table. */
372 (cgraph_node_set_element) GGC_NEW (struct cgraph_node_set_element_def);
373 element->node = node;
374 element->index = VEC_length (cgraph_node_ptr, set->nodes);
377 /* Insert into node vector. */
378 VEC_safe_push (cgraph_node_ptr, gc, set->nodes, node);
381 /* Remove cgraph_node NODE from cgraph_node_set SET. */
384 cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
386 void **slot, **last_slot;
387 cgraph_node_set_element element, last_element;
388 struct cgraph_node *last_node;
389 struct cgraph_node_set_element_def dummy;
392 slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
396 element = (cgraph_node_set_element) *slot;
397 gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
400 /* Remove from vector. We do this by swapping node with the last element
402 last_node = VEC_pop (cgraph_node_ptr, set->nodes);
403 if (last_node != node)
405 dummy.node = last_node;
406 last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
407 last_element = (cgraph_node_set_element) *last_slot;
408 gcc_assert (last_element);
410 /* Move the last element to the original spot of NODE. */
411 last_element->index = element->index;
412 VEC_replace (cgraph_node_ptr, set->nodes, last_element->index,
416 /* Remove element from hash table. */
417 htab_clear_slot (set->hashtab, slot);
421 /* Find NODE in SET and return an iterator to it if found. A null iterator
422 is returned if NODE is not in SET. */
424 cgraph_node_set_iterator
425 cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
428 struct cgraph_node_set_element_def dummy;
429 cgraph_node_set_element element;
430 cgraph_node_set_iterator csi;
433 slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
435 csi.index = (unsigned) ~0;
438 element = (cgraph_node_set_element) *slot;
439 gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
441 csi.index = element->index;
448 /* Dump content of SET to file F. */
451 dump_cgraph_node_set (FILE *f, cgraph_node_set set)
453 cgraph_node_set_iterator iter;
455 for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
457 struct cgraph_node *node = csi_node (iter);
458 dump_cgraph_node (f, node);
462 /* Dump content of SET to stderr. */
465 debug_cgraph_node_set (cgraph_node_set set)
467 dump_cgraph_node_set (stderr, set);