1 /* Basic IPA optimizations and utilities.
2 Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009 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
*processed
= (struct cgraph_node
*) (void *) 2;
125 struct cgraph_node
*node
, *next
;
126 bool changed
= false;
128 #ifdef ENABLE_CHECKING
132 fprintf (file
, "\nReclaiming functions:");
133 #ifdef ENABLE_CHECKING
134 for (node
= cgraph_nodes
; node
; node
= node
->next
)
135 gcc_assert (!node
->aux
);
137 for (node
= cgraph_nodes
; node
; node
= node
->next
)
138 if (!cgraph_can_remove_if_no_direct_calls_p (node
)
139 && ((!DECL_EXTERNAL (node
->decl
))
141 || before_inlining_p
))
143 gcc_assert (!node
->global
.inlined_to
);
146 node
->reachable
= true;
150 gcc_assert (!node
->aux
);
151 node
->reachable
= false;
154 /* Perform reachability analysis. As a special case do not consider
155 extern inline functions not inlined as live because we won't output
157 while (first
!= (void *) 1)
159 struct cgraph_edge
*e
;
161 first
= (struct cgraph_node
*) first
->aux
;
162 node
->aux
= processed
;
165 for (e
= node
->callees
; e
; e
= e
->next_callee
)
166 if (!e
->callee
->reachable
168 && (!e
->inline_failed
|| !e
->callee
->analyzed
169 || (!DECL_EXTERNAL (e
->callee
->decl
))
170 || before_inlining_p
))
172 bool prev_reachable
= e
->callee
->reachable
;
173 e
->callee
->reachable
|= node
->reachable
;
175 || (e
->callee
->aux
== processed
176 && prev_reachable
!= e
->callee
->reachable
))
178 e
->callee
->aux
= first
;
183 /* If any function in a comdat group is reachable, force
184 all other functions in the same comdat group to be
186 if (node
->same_comdat_group
188 && !node
->global
.inlined_to
)
190 for (next
= node
->same_comdat_group
;
192 next
= next
->same_comdat_group
)
193 if (!next
->reachable
)
197 next
->reachable
= true;
201 /* We can freely remove inline clones even if they are cloned, however if
202 function is clone of real clone, we must keep it around in order to
203 make materialize_clones produce function body with the changes
205 while (node
->clone_of
&& !node
->clone_of
->aux
&& !gimple_has_body_p (node
->decl
))
207 bool noninline
= node
->clone_of
->decl
!= node
->decl
;
208 node
= node
->clone_of
;
218 /* Remove unreachable nodes. Extern inline functions need special care;
219 Unreachable extern inline functions shall be removed.
220 Reachable extern inline functions we never inlined shall get their bodies
222 Reachable extern inline functions we sometimes inlined will be turned into
223 unanalyzed nodes so they look like for true extern functions to the rest
224 of code. Body of such functions is released via remove_node once the
225 inline clones are eliminated. */
226 for (node
= cgraph_nodes
; node
; node
= next
)
229 if (node
->aux
&& !node
->reachable
)
231 cgraph_node_remove_callees (node
);
232 node
->analyzed
= false;
233 node
->local
.inlinable
= false;
237 node
->global
.inlined_to
= NULL
;
239 fprintf (file
, " %s", cgraph_node_name (node
));
240 if (!node
->analyzed
|| !DECL_EXTERNAL (node
->decl
) || before_inlining_p
)
241 cgraph_remove_node (node
);
244 struct cgraph_edge
*e
;
246 /* See if there is reachable caller. */
247 for (e
= node
->callers
; e
; e
= e
->next_caller
)
251 /* If so, we need to keep node in the callgraph. */
252 if (e
|| node
->needed
)
254 struct cgraph_node
*clone
;
256 /* If there are still clones, we must keep body around.
257 Otherwise we can just remove the body but keep the clone. */
258 for (clone
= node
->clones
; clone
;
259 clone
= clone
->next_sibling_clone
)
264 cgraph_release_function_body (node
);
265 cgraph_node_remove_callees (node
);
266 node
->analyzed
= false;
267 node
->local
.inlinable
= false;
269 if (node
->prev_sibling_clone
)
270 node
->prev_sibling_clone
->next_sibling_clone
= node
->next_sibling_clone
;
271 else if (node
->clone_of
)
272 node
->clone_of
->clones
= node
->next_sibling_clone
;
273 if (node
->next_sibling_clone
)
274 node
->next_sibling_clone
->prev_sibling_clone
= node
->prev_sibling_clone
;
275 node
->clone_of
= NULL
;
276 node
->next_sibling_clone
= NULL
;
277 node
->prev_sibling_clone
= NULL
;
280 cgraph_remove_node (node
);
285 for (node
= cgraph_nodes
; node
; node
= node
->next
)
287 /* Inline clones might be kept around so their materializing allows further
288 cloning. If the function the clone is inlined into is removed, we need
289 to turn it into normal cone. */
290 if (node
->global
.inlined_to
293 gcc_assert (node
->clones
);
294 node
->global
.inlined_to
= NULL
;
295 update_inlined_to_pointer (node
, node
);
299 #ifdef ENABLE_CHECKING
303 /* Reclaim alias pairs for functions that have disappeared from the
305 remove_unreachable_alias_pairs ();
311 cgraph_externally_visible_p (struct cgraph_node
*node
, bool whole_program
)
313 if (!node
->local
.finalized
)
315 if (!DECL_COMDAT (node
->decl
)
316 && (!TREE_PUBLIC (node
->decl
) || DECL_EXTERNAL (node
->decl
)))
320 /* COMDAT functions must be shared only if they have address taken,
321 otherwise we can produce our own private implementation with
323 if (DECL_COMDAT (node
->decl
))
325 if (node
->address_taken
|| !node
->analyzed
)
327 if (node
->same_comdat_group
)
329 struct cgraph_node
*next
;
331 /* If more than one function is in the same COMDAT group, it must
332 be shared even if just one function in the comdat group has
334 for (next
= node
->same_comdat_group
;
336 next
= next
->same_comdat_group
)
337 if (next
->address_taken
|| !next
->analyzed
)
341 if (MAIN_NAME_P (DECL_NAME (node
->decl
)))
343 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (node
->decl
)))
348 /* Mark visibility of all functions.
350 A local function is one whose calls can occur only in the current
351 compilation unit and all its calls are explicit, so we can change
352 its calling convention. We simply mark all static functions whose
353 address is not taken as local.
355 We also change the TREE_PUBLIC flag of all declarations that are public
356 in language point of view but we want to overwrite this default
357 via visibilities for the backend point of view. */
360 function_and_variable_visibility (bool whole_program
)
362 struct cgraph_node
*node
;
363 struct varpool_node
*vnode
;
365 for (node
= cgraph_nodes
; node
; node
= node
->next
)
367 /* C++ FE on lack of COMDAT support create local COMDAT functions
368 (that ought to be shared but can not due to object format
369 limitations). It is neccesary to keep the flag to make rest of C++ FE
370 happy. Clear the flag here to avoid confusion in middle-end. */
371 if (DECL_COMDAT (node
->decl
) && !TREE_PUBLIC (node
->decl
))
372 DECL_COMDAT (node
->decl
) = 0;
373 /* For external decls stop tracking same_comdat_group, it doesn't matter
374 what comdat group they are in when they won't be emitted in this TU,
375 and simplifies later passes. */
376 if (node
->same_comdat_group
&& DECL_EXTERNAL (node
->decl
))
378 struct cgraph_node
*n
= node
, *next
;
381 /* If at least one of same comdat group functions is external,
382 all of them have to be, otherwise it is a front-end bug. */
383 gcc_assert (DECL_EXTERNAL (n
->decl
));
384 next
= n
->same_comdat_group
;
385 n
->same_comdat_group
= NULL
;
390 gcc_assert ((!DECL_WEAK (node
->decl
) && !DECL_COMDAT (node
->decl
))
391 || TREE_PUBLIC (node
->decl
) || DECL_EXTERNAL (node
->decl
));
392 if (cgraph_externally_visible_p (node
, whole_program
))
394 gcc_assert (!node
->global
.inlined_to
);
395 node
->local
.externally_visible
= true;
398 node
->local
.externally_visible
= false;
399 if (!node
->local
.externally_visible
&& node
->analyzed
400 && !DECL_EXTERNAL (node
->decl
))
402 gcc_assert (whole_program
|| !TREE_PUBLIC (node
->decl
));
403 cgraph_make_decl_local (node
->decl
);
405 node
->local
.local
= (cgraph_only_called_directly_p (node
)
407 && !DECL_EXTERNAL (node
->decl
)
408 && !node
->local
.externally_visible
);
410 for (vnode
= varpool_nodes_queue
; vnode
; vnode
= vnode
->next_needed
)
412 if (!vnode
->finalized
)
414 gcc_assert ((!DECL_WEAK (vnode
->decl
) && !DECL_COMMON (vnode
->decl
))
415 || TREE_PUBLIC (vnode
->decl
) || DECL_EXTERNAL (vnode
->decl
));
417 && (DECL_COMDAT (vnode
->decl
) || TREE_PUBLIC (vnode
->decl
))
419 /* We can privatize comdat readonly variables whose address is not taken,
420 but doing so is not going to bring us optimization oppurtunities until
421 we start reordering datastructures. */
422 || DECL_COMDAT (vnode
->decl
)
423 || DECL_WEAK (vnode
->decl
)
424 || lookup_attribute ("externally_visible",
425 DECL_ATTRIBUTES (vnode
->decl
))))
426 vnode
->externally_visible
= true;
428 vnode
->externally_visible
= false;
429 if (!vnode
->externally_visible
)
431 gcc_assert (whole_program
|| !TREE_PUBLIC (vnode
->decl
));
432 cgraph_make_decl_local (vnode
->decl
);
434 gcc_assert (TREE_STATIC (vnode
->decl
));
439 fprintf (dump_file
, "\nMarking local functions:");
440 for (node
= cgraph_nodes
; node
; node
= node
->next
)
441 if (node
->local
.local
)
442 fprintf (dump_file
, " %s", cgraph_node_name (node
));
443 fprintf (dump_file
, "\n\n");
444 fprintf (dump_file
, "\nMarking externally visible functions:");
445 for (node
= cgraph_nodes
; node
; node
= node
->next
)
446 if (node
->local
.externally_visible
)
447 fprintf (dump_file
, " %s", cgraph_node_name (node
));
448 fprintf (dump_file
, "\n\n");
449 fprintf (dump_file
, "\nMarking externally visible variables:");
450 for (vnode
= varpool_nodes_queue
; vnode
; vnode
= vnode
->next_needed
)
451 if (vnode
->externally_visible
)
452 fprintf (dump_file
, " %s", varpool_node_name (vnode
));
453 fprintf (dump_file
, "\n\n");
455 cgraph_function_flags_ready
= true;
459 /* Local function pass handling visibilities. This happens before LTO streaming
460 so in particular -fwhole-program should be ignored at this level. */
463 local_function_and_variable_visibility (void)
465 return function_and_variable_visibility (flag_whole_program
&& !flag_lto
&& !flag_whopr
);
468 struct simple_ipa_opt_pass pass_ipa_function_and_variable_visibility
=
472 "visibility", /* name */
474 local_function_and_variable_visibility
,/* execute */
477 0, /* static_pass_number */
478 TV_CGRAPHOPT
, /* tv_id */
479 0, /* properties_required */
480 0, /* properties_provided */
481 0, /* properties_destroyed */
482 0, /* todo_flags_start */
483 TODO_remove_functions
| TODO_dump_cgraph
/* todo_flags_finish */
487 /* Do not re-run on ltrans stage. */
490 gate_whole_program_function_and_variable_visibility (void)
495 /* Bring functionss local at LTO time whith -fwhole-program. */
498 whole_program_function_and_variable_visibility (void)
500 struct cgraph_node
*node
;
501 struct varpool_node
*vnode
;
503 function_and_variable_visibility (flag_whole_program
);
505 for (node
= cgraph_nodes
; node
; node
= node
->next
)
506 if ((node
->local
.externally_visible
&& !DECL_COMDAT (node
->decl
))
507 && node
->local
.finalized
)
508 cgraph_mark_needed_node (node
);
509 for (vnode
= varpool_nodes_queue
; vnode
; vnode
= vnode
->next_needed
)
510 if (vnode
->externally_visible
&& !DECL_COMDAT (vnode
->decl
))
511 varpool_mark_needed_node (vnode
);
514 fprintf (dump_file
, "\nNeeded variables:");
515 for (vnode
= varpool_nodes_queue
; vnode
; vnode
= vnode
->next_needed
)
517 fprintf (dump_file
, " %s", varpool_node_name (vnode
));
518 fprintf (dump_file
, "\n\n");
523 struct ipa_opt_pass_d pass_ipa_whole_program_visibility
=
527 "whole-program", /* name */
528 gate_whole_program_function_and_variable_visibility
,/* gate */
529 whole_program_function_and_variable_visibility
,/* execute */
532 0, /* static_pass_number */
533 TV_CGRAPHOPT
, /* tv_id */
534 0, /* properties_required */
535 0, /* properties_provided */
536 0, /* properties_destroyed */
537 0, /* todo_flags_start */
538 TODO_dump_cgraph
| TODO_remove_functions
/* todo_flags_finish */
540 NULL
, /* generate_summary */
541 NULL
, /* write_summary */
542 NULL
, /* read_summary */
543 NULL
, /* function_read_summary */
544 NULL
, /* stmt_fixup */
546 NULL
, /* function_transform */
547 NULL
, /* variable_transform */
550 /* Hash a cgraph node set element. */
553 hash_cgraph_node_set_element (const void *p
)
555 const_cgraph_node_set_element element
= (const_cgraph_node_set_element
) p
;
556 return htab_hash_pointer (element
->node
);
559 /* Compare two cgraph node set elements. */
562 eq_cgraph_node_set_element (const void *p1
, const void *p2
)
564 const_cgraph_node_set_element e1
= (const_cgraph_node_set_element
) p1
;
565 const_cgraph_node_set_element e2
= (const_cgraph_node_set_element
) p2
;
567 return e1
->node
== e2
->node
;
570 /* Create a new cgraph node set. */
573 cgraph_node_set_new (void)
575 cgraph_node_set new_node_set
;
577 new_node_set
= GGC_NEW (struct cgraph_node_set_def
);
578 new_node_set
->hashtab
= htab_create_ggc (10,
579 hash_cgraph_node_set_element
,
580 eq_cgraph_node_set_element
,
582 new_node_set
->nodes
= NULL
;
586 /* Add cgraph_node NODE to cgraph_node_set SET. */
589 cgraph_node_set_add (cgraph_node_set set
, struct cgraph_node
*node
)
592 cgraph_node_set_element element
;
593 struct cgraph_node_set_element_def dummy
;
596 slot
= htab_find_slot (set
->hashtab
, &dummy
, INSERT
);
598 if (*slot
!= HTAB_EMPTY_ENTRY
)
600 element
= (cgraph_node_set_element
) *slot
;
601 gcc_assert (node
== element
->node
602 && (VEC_index (cgraph_node_ptr
, set
->nodes
, element
->index
)
607 /* Insert node into hash table. */
609 (cgraph_node_set_element
) GGC_NEW (struct cgraph_node_set_element_def
);
610 element
->node
= node
;
611 element
->index
= VEC_length (cgraph_node_ptr
, set
->nodes
);
614 /* Insert into node vector. */
615 VEC_safe_push (cgraph_node_ptr
, gc
, set
->nodes
, node
);
618 /* Remove cgraph_node NODE from cgraph_node_set SET. */
621 cgraph_node_set_remove (cgraph_node_set set
, struct cgraph_node
*node
)
623 void **slot
, **last_slot
;
624 cgraph_node_set_element element
, last_element
;
625 struct cgraph_node
*last_node
;
626 struct cgraph_node_set_element_def dummy
;
629 slot
= htab_find_slot (set
->hashtab
, &dummy
, NO_INSERT
);
633 element
= (cgraph_node_set_element
) *slot
;
634 gcc_assert (VEC_index (cgraph_node_ptr
, set
->nodes
, element
->index
)
637 /* Remove from vector. We do this by swapping node with the last element
639 last_node
= VEC_pop (cgraph_node_ptr
, set
->nodes
);
640 if (last_node
!= node
)
642 dummy
.node
= last_node
;
643 last_slot
= htab_find_slot (set
->hashtab
, &dummy
, NO_INSERT
);
644 last_element
= (cgraph_node_set_element
) *last_slot
;
645 gcc_assert (last_element
);
647 /* Move the last element to the original spot of NODE. */
648 last_element
->index
= element
->index
;
649 VEC_replace (cgraph_node_ptr
, set
->nodes
, last_element
->index
,
653 /* Remove element from hash table. */
654 htab_clear_slot (set
->hashtab
, slot
);
658 /* Find NODE in SET and return an iterator to it if found. A null iterator
659 is returned if NODE is not in SET. */
661 cgraph_node_set_iterator
662 cgraph_node_set_find (cgraph_node_set set
, struct cgraph_node
*node
)
665 struct cgraph_node_set_element_def dummy
;
666 cgraph_node_set_element element
;
667 cgraph_node_set_iterator csi
;
670 slot
= htab_find_slot (set
->hashtab
, &dummy
, NO_INSERT
);
672 csi
.index
= (unsigned) ~0;
675 element
= (cgraph_node_set_element
) *slot
;
676 gcc_assert (VEC_index (cgraph_node_ptr
, set
->nodes
, element
->index
)
678 csi
.index
= element
->index
;
685 /* Dump content of SET to file F. */
688 dump_cgraph_node_set (FILE *f
, cgraph_node_set set
)
690 cgraph_node_set_iterator iter
;
692 for (iter
= csi_start (set
); !csi_end_p (iter
); csi_next (&iter
))
694 struct cgraph_node
*node
= csi_node (iter
);
695 dump_cgraph_node (f
, node
);
699 /* Dump content of SET to stderr. */
702 debug_cgraph_node_set (cgraph_node_set set
)
704 dump_cgraph_node_set (stderr
, set
);