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)
56 || (!cgraph_only_called_directly_p (node)
57 && !node->address_taken)))
63 node->aux = node->callers;
66 while (node2->aux != &last)
68 edge = (struct cgraph_edge *) node2->aux;
69 if (edge->next_caller)
70 node2->aux = edge->next_caller;
73 if (!edge->caller->aux)
75 if (!edge->caller->callers)
76 edge->caller->aux = &last;
78 edge->caller->aux = edge->caller->callers;
79 stack[stack_size++] = node2;
84 if (node2->aux == &last)
86 order[order_pos++] = node2;
88 node2 = stack[--stack_size];
95 for (node = cgraph_nodes; node; node = node->next)
100 /* Look for all functions inlined to NODE and update their inlined_to pointers
104 update_inlined_to_pointer (struct cgraph_node *node, struct cgraph_node *inlined_to)
106 struct cgraph_edge *e;
107 for (e = node->callees; e; e = e->next_callee)
108 if (e->callee->global.inlined_to)
110 e->callee->global.inlined_to = inlined_to;
111 update_inlined_to_pointer (e->callee, inlined_to);
115 /* Perform reachability analysis and reclaim all unreachable nodes.
116 If BEFORE_INLINING_P is true this function is called before inlining
117 decisions has been made. If BEFORE_INLINING_P is false this function also
118 removes unneeded bodies of extern inline functions. */
121 cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file)
123 struct cgraph_node *first = (struct cgraph_node *) (void *) 1;
124 struct cgraph_node *node, *next;
125 bool changed = false;
127 #ifdef ENABLE_CHECKING
131 fprintf (file, "\nReclaiming functions:");
132 #ifdef ENABLE_CHECKING
133 for (node = cgraph_nodes; node; node = node->next)
134 gcc_assert (!node->aux);
136 for (node = cgraph_nodes; node; node = node->next)
137 if (!cgraph_can_remove_if_no_direct_calls_p (node)
138 && ((!DECL_EXTERNAL (node->decl))
140 || before_inlining_p))
142 gcc_assert (!node->global.inlined_to);
147 gcc_assert (!node->aux);
149 /* Perform reachability analysis. As a special case do not consider
150 extern inline functions not inlined as live because we won't output
152 while (first != (void *) 1)
154 struct cgraph_edge *e;
156 first = (struct cgraph_node *) first->aux;
158 for (e = node->callees; e; e = e->next_callee)
161 && (!e->inline_failed || !e->callee->analyzed
162 || (!DECL_EXTERNAL (e->callee->decl))
163 || before_inlining_p))
165 e->callee->aux = first;
168 while (node->clone_of && !node->clone_of->aux && !gimple_has_body_p (node->decl))
170 node = node->clone_of;
176 /* Remove unreachable nodes. Extern inline functions need special care;
177 Unreachable extern inline functions shall be removed.
178 Reachable extern inline functions we never inlined shall get their bodies
180 Reachable extern inline functions we sometimes inlined will be turned into
181 unanalyzed nodes so they look like for true extern functions to the rest
182 of code. Body of such functions is released via remove_node once the
183 inline clones are eliminated. */
184 for (node = cgraph_nodes; node; node = next)
189 node->global.inlined_to = NULL;
191 fprintf (file, " %s", cgraph_node_name (node));
192 if (!node->analyzed || !DECL_EXTERNAL (node->decl)
193 || before_inlining_p)
194 cgraph_remove_node (node);
197 struct cgraph_edge *e;
199 /* See if there is reachable caller. */
200 for (e = node->callers; e; e = e->next_caller)
204 /* If so, we need to keep node in the callgraph. */
205 if (e || node->needed)
207 struct cgraph_node *clone;
209 /* If there are still clones, we must keep body around.
210 Otherwise we can just remove the body but keep the clone. */
211 for (clone = node->clones; clone;
212 clone = clone->next_sibling_clone)
217 cgraph_release_function_body (node);
218 cgraph_node_remove_callees (node);
219 node->analyzed = false;
220 node->local.inlinable = false;
224 cgraph_remove_node (node);
229 for (node = cgraph_nodes; node; node = node->next)
231 /* Inline clones might be kept around so their materializing allows further
232 cloning. If the function the clone is inlined into is removed, we need
233 to turn it into normal cone. */
234 if (node->global.inlined_to
237 gcc_assert (node->clones);
238 node->global.inlined_to = NULL;
239 update_inlined_to_pointer (node, node);
243 #ifdef ENABLE_CHECKING
247 /* Reclaim alias pairs for functions that have disappeared from the
249 remove_unreachable_alias_pairs ();
255 cgraph_externally_visible_p (struct cgraph_node *node, bool whole_program)
257 if (!node->local.finalized)
259 if (!DECL_COMDAT (node->decl)
260 && (!TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl)))
264 /* COMDAT functions must be shared only if they have address taken,
265 otherwise we can produce our own private implementation with
267 if (DECL_COMDAT (node->decl) && (node->address_taken || !node->analyzed))
269 if (MAIN_NAME_P (DECL_NAME (node->decl)))
271 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (node->decl)))
276 /* Mark visibility of all functions.
278 A local function is one whose calls can occur only in the current
279 compilation unit and all its calls are explicit, so we can change
280 its calling convention. We simply mark all static functions whose
281 address is not taken as local.
283 We also change the TREE_PUBLIC flag of all declarations that are public
284 in language point of view but we want to overwrite this default
285 via visibilities for the backend point of view. */
288 function_and_variable_visibility (bool whole_program)
290 struct cgraph_node *node;
291 struct varpool_node *vnode;
293 for (node = cgraph_nodes; node; node = node->next)
295 /* C++ FE on lack of COMDAT support create local COMDAT functions
296 (that ought to be shared but can not due to object format
297 limitations). It is neccesary to keep the flag to make rest of C++ FE
298 happy. Clear the flag here to avoid confusion in middle-end. */
299 if (DECL_COMDAT (node->decl) && !TREE_PUBLIC (node->decl))
300 DECL_COMDAT (node->decl) = 0;
301 gcc_assert ((!DECL_WEAK (node->decl) && !DECL_COMDAT (node->decl))
302 || TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl));
303 if (cgraph_externally_visible_p (node, whole_program))
305 gcc_assert (!node->global.inlined_to);
306 node->local.externally_visible = true;
309 node->local.externally_visible = false;
310 if (!node->local.externally_visible && node->analyzed
311 && !DECL_EXTERNAL (node->decl))
313 gcc_assert (whole_program || !TREE_PUBLIC (node->decl));
314 TREE_PUBLIC (node->decl) = 0;
315 DECL_COMDAT (node->decl) = 0;
316 DECL_WEAK (node->decl) = 0;
318 node->local.local = (cgraph_only_called_directly_p (node)
320 && !DECL_EXTERNAL (node->decl)
321 && !node->local.externally_visible);
323 for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
325 if (!vnode->finalized)
327 gcc_assert ((!DECL_WEAK (vnode->decl) && !DECL_COMMON (vnode->decl))
328 || TREE_PUBLIC (vnode->decl) || DECL_EXTERNAL (vnode->decl));
330 && (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl))
332 /* We can privatize comdat readonly variables whose address is not taken,
333 but doing so is not going to bring us optimization oppurtunities until
334 we start reordering datastructures. */
335 || DECL_COMDAT (vnode->decl)
336 || DECL_WEAK (vnode->decl)
337 || lookup_attribute ("externally_visible",
338 DECL_ATTRIBUTES (vnode->decl))))
339 vnode->externally_visible = true;
341 vnode->externally_visible = false;
342 if (!vnode->externally_visible)
344 gcc_assert (whole_program || !TREE_PUBLIC (vnode->decl));
345 TREE_PUBLIC (vnode->decl) = 0;
346 DECL_COMMON (vnode->decl) = 0;
348 gcc_assert (TREE_STATIC (vnode->decl));
353 fprintf (dump_file, "\nMarking local functions:");
354 for (node = cgraph_nodes; node; node = node->next)
355 if (node->local.local)
356 fprintf (dump_file, " %s", cgraph_node_name (node));
357 fprintf (dump_file, "\n\n");
358 fprintf (dump_file, "\nMarking externally visible functions:");
359 for (node = cgraph_nodes; node; node = node->next)
360 if (node->local.externally_visible)
361 fprintf (dump_file, " %s", cgraph_node_name (node));
362 fprintf (dump_file, "\n\n");
363 fprintf (dump_file, "\nMarking externally visible variables:");
364 for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
365 if (vnode->externally_visible)
366 fprintf (dump_file, " %s", varpool_node_name (vnode));
367 fprintf (dump_file, "\n\n");
369 cgraph_function_flags_ready = true;
373 /* Local function pass handling visibilities. This happens before LTO streaming
374 so in particular -fwhole-program should be ignored at this level. */
377 local_function_and_variable_visibility (void)
379 return function_and_variable_visibility (flag_whole_program && !flag_lto && !flag_whopr);
382 struct simple_ipa_opt_pass pass_ipa_function_and_variable_visibility =
386 "visibility", /* name */
388 local_function_and_variable_visibility,/* execute */
391 0, /* static_pass_number */
392 TV_CGRAPHOPT, /* tv_id */
393 0, /* properties_required */
394 0, /* properties_provided */
395 0, /* properties_destroyed */
396 0, /* todo_flags_start */
397 TODO_remove_functions | TODO_dump_cgraph/* todo_flags_finish */
401 /* Do not re-run on ltrans stage. */
404 gate_whole_program_function_and_variable_visibility (void)
409 /* Bring functionss local at LTO time whith -fwhole-program. */
412 whole_program_function_and_variable_visibility (void)
414 struct cgraph_node *node;
415 struct varpool_node *vnode;
417 function_and_variable_visibility (flag_whole_program);
419 for (node = cgraph_nodes; node; node = node->next)
420 if ((node->local.externally_visible && !DECL_COMDAT (node->decl))
421 && node->local.finalized)
422 cgraph_mark_needed_node (node);
423 for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
424 if (vnode->externally_visible && !DECL_COMDAT (vnode->decl))
425 varpool_mark_needed_node (vnode);
428 fprintf (dump_file, "\nNeeded variables:");
429 for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
431 fprintf (dump_file, " %s", varpool_node_name (vnode));
432 fprintf (dump_file, "\n\n");
437 struct ipa_opt_pass_d pass_ipa_whole_program_visibility =
441 "whole-program", /* name */
442 gate_whole_program_function_and_variable_visibility,/* gate */
443 whole_program_function_and_variable_visibility,/* execute */
446 0, /* static_pass_number */
447 TV_CGRAPHOPT, /* tv_id */
448 0, /* properties_required */
449 0, /* properties_provided */
450 0, /* properties_destroyed */
451 0, /* todo_flags_start */
452 TODO_dump_cgraph | TODO_remove_functions/* todo_flags_finish */
454 NULL, /* generate_summary */
455 NULL, /* write_summary */
456 NULL, /* read_summary */
457 NULL, /* function_read_summary */
458 NULL, /* stmt_fixup */
460 NULL, /* function_transform */
461 NULL, /* variable_transform */
464 /* Hash a cgraph node set element. */
467 hash_cgraph_node_set_element (const void *p)
469 const_cgraph_node_set_element element = (const_cgraph_node_set_element) p;
470 return htab_hash_pointer (element->node);
473 /* Compare two cgraph node set elements. */
476 eq_cgraph_node_set_element (const void *p1, const void *p2)
478 const_cgraph_node_set_element e1 = (const_cgraph_node_set_element) p1;
479 const_cgraph_node_set_element e2 = (const_cgraph_node_set_element) p2;
481 return e1->node == e2->node;
484 /* Create a new cgraph node set. */
487 cgraph_node_set_new (void)
489 cgraph_node_set new_node_set;
491 new_node_set = GGC_NEW (struct cgraph_node_set_def);
492 new_node_set->hashtab = htab_create_ggc (10,
493 hash_cgraph_node_set_element,
494 eq_cgraph_node_set_element,
496 new_node_set->nodes = NULL;
500 /* Add cgraph_node NODE to cgraph_node_set SET. */
503 cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
506 cgraph_node_set_element element;
507 struct cgraph_node_set_element_def dummy;
510 slot = htab_find_slot (set->hashtab, &dummy, INSERT);
512 if (*slot != HTAB_EMPTY_ENTRY)
514 element = (cgraph_node_set_element) *slot;
515 gcc_assert (node == element->node
516 && (VEC_index (cgraph_node_ptr, set->nodes, element->index)
521 /* Insert node into hash table. */
523 (cgraph_node_set_element) GGC_NEW (struct cgraph_node_set_element_def);
524 element->node = node;
525 element->index = VEC_length (cgraph_node_ptr, set->nodes);
528 /* Insert into node vector. */
529 VEC_safe_push (cgraph_node_ptr, gc, set->nodes, node);
532 /* Remove cgraph_node NODE from cgraph_node_set SET. */
535 cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
537 void **slot, **last_slot;
538 cgraph_node_set_element element, last_element;
539 struct cgraph_node *last_node;
540 struct cgraph_node_set_element_def dummy;
543 slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
547 element = (cgraph_node_set_element) *slot;
548 gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
551 /* Remove from vector. We do this by swapping node with the last element
553 last_node = VEC_pop (cgraph_node_ptr, set->nodes);
554 if (last_node != node)
556 dummy.node = last_node;
557 last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
558 last_element = (cgraph_node_set_element) *last_slot;
559 gcc_assert (last_element);
561 /* Move the last element to the original spot of NODE. */
562 last_element->index = element->index;
563 VEC_replace (cgraph_node_ptr, set->nodes, last_element->index,
567 /* Remove element from hash table. */
568 htab_clear_slot (set->hashtab, slot);
572 /* Find NODE in SET and return an iterator to it if found. A null iterator
573 is returned if NODE is not in SET. */
575 cgraph_node_set_iterator
576 cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
579 struct cgraph_node_set_element_def dummy;
580 cgraph_node_set_element element;
581 cgraph_node_set_iterator csi;
584 slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
586 csi.index = (unsigned) ~0;
589 element = (cgraph_node_set_element) *slot;
590 gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
592 csi.index = element->index;
599 /* Dump content of SET to file F. */
602 dump_cgraph_node_set (FILE *f, cgraph_node_set set)
604 cgraph_node_set_iterator iter;
606 for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
608 struct cgraph_node *node = csi_node (iter);
609 dump_cgraph_node (f, node);
613 /* Dump content of SET to stderr. */
616 debug_cgraph_node_set (cgraph_node_set set)
618 dump_cgraph_node_set (stderr, set);